Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5677 > unrolled thread

really? (lame question about primes)

Back to article view | Back to comp.programming

Contents

  really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-08-31 12:07 -0700
    Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-08-31 23:23 +0100
      Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 01:18 -0700
        Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-01 11:01 +0200
          Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 12:20 +0100
            Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-01 15:48 +0100
              Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:26 -0700
                Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-09-02 02:12 -0500
                  Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 08:38 +0100
                    Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:03 +0200
            Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 13:24 -0700
              Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 22:27 +0100
                Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 15:02 -0700
                  Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-01 23:20 +0100
                    Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:22 +0200
                      Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-01 17:18 -0700
                        Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:19 +0100
                          Re: really? (lame question about primes) James Dow Allen <gmail@jamesdowallen.nospam> - 2015-09-02 12:42 +0000
                            Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 14:21 +0100
                              Re: really? (lame question about primes) Johannes Bauer <dfnsonfsduifb@gmx.de> - 2015-09-02 17:45 +0200
                                Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 18:06 +0100
                                  Re: really? (lame question about primes) James Dow Allen <jdallen2000@yahoo.com> - 2015-09-03 17:05 -0700
                                    Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-04 02:18 +0200
                                      Re: really? (lame question about primes) Chad <cdalten@gmail.com> - 2015-09-03 22:37 -0700
                                        Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-03 23:49 -0700
                                          Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-04 00:18 -0700
                                        Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-04 08:25 +0100
                            Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 14:36 +0100
                              Re: really? (lame question about primes) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-09-02 16:49 +0100
                                Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 17:32 +0100
              Re: really? (lame question about primes) Kaz Kylheku <kaz@kylheku.com> - 2015-09-01 22:55 +0000
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 01:15 +0200
            Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 03:19 +0200
              Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 02:37 +0100
                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 11:24 +0200
                  Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 10:42 +0100
                    Re: really? (lame question about primes) fir <profesor.fir@gmail.com> - 2015-09-02 03:01 -0700
                    Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 12:28 +0200
                    Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 14:12 +0200
                      Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:19 +0100
                        Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 14:56 +0200
                          Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 15:47 +0200
                            Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 16:27 +0200
                              Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-02 16:37 +0200
                                Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-02 17:01 +0200
                                  Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 10:55 +0200
                                    Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:05 +0100
                                      Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 11:49 +0200
                                        Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-03 10:54 +0100
                                          Re: really? (lame question about primes) David Brown <david.brown@hesbynett.no> - 2015-09-03 13:22 +0200
                                    Re: really? (lame question about primes) bartekltg <bartek@gmail.com> - 2015-09-03 13:58 +0200
                      Re: really? (lame question about primes) Richard Heathfield <rjh@cpax.org.uk> - 2015-09-02 13:34 +0100
    Re: really? (lame question about primes) Robert Wessel <robertwessel2@yahoo.com> - 2015-08-31 23:10 -0500

Page 3 of 3 — ← Prev page 1 2 [3]

#5716

On 02.09.2015 14:19, Richard Heathfield wrote:
> On 02/09/2015 13:12, David Brown wrote:
>>
> <snip>
>>
>> There are a number of ways of doing this check faster than the
>> bit-for-bit long division you suggested elsewhere,
>
> The advantage of that way is that it's easy to explain, and relatively
> easy to implement. Having said that, I *haven't* implemented it (in
> software). My bignum library uses Algorithm D, from TAOCP II.

I think explain something by using wrong algorithm can hurt
someone who think, so propably everyone who is listening to
'how to factorize an integer;-)'

But we can resurect this idea.

Table of all n-digits prime can be too big for the universe,
so we have to generate it. One ot the simplest method is
to implement 'nextprime' - function that get the next odd*)
number and run fast primality test (Miller-Rabin),
repeat it until the number is pseudoprime.

In similar way you can write 'prevprime(n)', a function
that compute the greatest pseudoprime smaller than n.

Your algorithm change to this:

C - a number to factorize
A = smallest n-digits number
B = greatest n-digits number

while (A<=B)
{
    D = A*B;
    if (D==C) return {A,B};
    if (D<C) A = nextprime(A);
    elseif (D>C) B = prevprime(B);
}
return {no solution}.


This algorithm runs twice as many primality tests as standard one,
but have the same complexity and do not use any division.
But I'm prety sure it still is slower than the one with divisions.


*) and propably mod 3=0, mod 5=0...

bartekltg

[toc] | [prev] | [next] | [standalone]

#5720

On 02/09/15 14:56, bartekltg wrote:
> On 02.09.2015 14:19, Richard Heathfield wrote:
>> On 02/09/2015 13:12, David Brown wrote:
>>>
>> <snip>
>>>
>>> There are a number of ways of doing this check faster than the
>>> bit-for-bit long division you suggested elsewhere,
>>
>> The advantage of that way is that it's easy to explain, and relatively
>> easy to implement. Having said that, I *haven't* implemented it (in
>> software). My bignum library uses Algorithm D, from TAOCP II.
> 
> I think explain something by using wrong algorithm can hurt
> someone who think, so propably everyone who is listening to
> 'how to factorize an integer;-)'
> 
> But we can resurect this idea.
> 
> Table of all n-digits prime can be too big for the universe,
> so we have to generate it. One ot the simplest method is
> to implement 'nextprime' - function that get the next odd*)
> number and run fast primality test (Miller-Rabin),
> repeat it until the number is pseudoprime.
> 

The principle here is that to find the factors of C, we run through all
primes A up to sqrt(C), and test if C % A == 0.  (It may be that there
are other faster algorithms, but I don't know of any.)  If you know for
sure the number of digits in A, then you could start 10^(noOfDigits-1),
but that would only save 10% of the test time.

Testing for the primality of each A is going to take a great deal more
time than simply trying C % A == 0, even with a probable prime test.  It
is simply not worth doing.

What would be worth doing, I think, is to keep a track of A % p for p in
the first n primes.  As you run through the A's, adding 2 to A each
step, you add 2 to each of these remainders in your tracking array.  If
these hit 0 (modulo their prime), then A is clearly non-prime and you
can skip it.  This will let you skip a number of your test divisions
with relatively little work - as you make that array of n primes bigger,
you cut out yet more divisions.  However, there is going to be a point
where doing this tracking for the modulo A % p will cost more (in memory
or speed) than 1/p times the cost of calculating C % A - and when you
reach that, you don't want to track any more modulos.

I suspect there is scope for some interesting data structures to hold
this list of modulos, rather than a simple array - perhaps a priority
queue in a Fibonacci heap?

[toc] | [prev] | [next] | [standalone]

#5721

On 02.09.2015 15:47, David Brown wrote:
> On 02/09/15 14:56, bartekltg wrote:
>> On 02.09.2015 14:19, Richard Heathfield wrote:
>>> On 02/09/2015 13:12, David Brown wrote:
>>>>
>>> <snip>
>>>>
>>>> There are a number of ways of doing this check faster than the
>>>> bit-for-bit long division you suggested elsewhere,
>>>
>>> The advantage of that way is that it's easy to explain, and relatively
>>> easy to implement. Having said that, I *haven't* implemented it (in
>>> software). My bignum library uses Algorithm D, from TAOCP II.
>>
>> I think explain something by using wrong algorithm can hurt
>> someone who think, so propably everyone who is listening to
>> 'how to factorize an integer;-)'
>>
>> But we can resurect this idea.
>>
>> Table of all n-digits prime can be too big for the universe,
>> so we have to generate it. One ot the simplest method is
>> to implement 'nextprime' - function that get the next odd*)
>> number and run fast primality test (Miller-Rabin),
>> repeat it until the number is pseudoprime.
>>
>
> The principle here is that to find the factors of C, we run through all
> primes A up to sqrt(C), and test if C % A == 0.  (It may be that there
> are other faster algorithms, but I don't know of any.)  If you know for
> sure the number of digits in A, then you could start 10^(noOfDigits-1),
> but that would only save 10% of the test time.
>
> Testing for the primality of each A is going to take a great deal more
> time than simply trying C % A == 0, even with a probable prime test.  It
> is simply not worth doing.
>
> What would be worth doing, I think, is to keep a track of A % p for p in
> the first n primes.  As you run through the A's, adding 2 to A each
> step, you add 2 to each of these remainders in your tracking array.  If
> these hit 0 (modulo their prime), then A is clearly non-prime and you
> can skip it.  This will let you skip a number of your test divisions
> with relatively little work - as you make that array of n primes bigger,
> you cut out yet more divisions.  However, there is going to be a point
> where doing this tracking for the modulo A % p will cost more (in memory
> or speed) than 1/p times the cost of calculating C % A - and when you
> reach that, you don't want to track any more modulos.
>
> I suspect there is scope for some interesting data structures to hold
> this list of modulos, rather than a simple array - perhaps a priority
> queue in a Fibonacci heap?


Yes, this is the "standard" algorithm I was talking about, in the last
post I even mentioned the heuristic you described it the third
paragraph.
Are you sure you wanted to post it as the answer to my post?

bartekltg

[toc] | [prev] | [next] | [standalone]

#5722

On 02/09/15 16:27, bartekltg wrote:
> On 02.09.2015 15:47, David Brown wrote:
>> On 02/09/15 14:56, bartekltg wrote:
>>> On 02.09.2015 14:19, Richard Heathfield wrote:
>>>> On 02/09/2015 13:12, David Brown wrote:
>>>>>
>>>> <snip>
>>>>>
>>>>> There are a number of ways of doing this check faster than the
>>>>> bit-for-bit long division you suggested elsewhere,
>>>>
>>>> The advantage of that way is that it's easy to explain, and relatively
>>>> easy to implement. Having said that, I *haven't* implemented it (in
>>>> software). My bignum library uses Algorithm D, from TAOCP II.
>>>
>>> I think explain something by using wrong algorithm can hurt
>>> someone who think, so propably everyone who is listening to
>>> 'how to factorize an integer;-)'
>>>
>>> But we can resurect this idea.
>>>
>>> Table of all n-digits prime can be too big for the universe,
>>> so we have to generate it. One ot the simplest method is
>>> to implement 'nextprime' - function that get the next odd*)
>>> number and run fast primality test (Miller-Rabin),
>>> repeat it until the number is pseudoprime.
>>>
>>
>> The principle here is that to find the factors of C, we run through all
>> primes A up to sqrt(C), and test if C % A == 0.  (It may be that there
>> are other faster algorithms, but I don't know of any.)  If you know for
>> sure the number of digits in A, then you could start 10^(noOfDigits-1),
>> but that would only save 10% of the test time.
>>
>> Testing for the primality of each A is going to take a great deal more
>> time than simply trying C % A == 0, even with a probable prime test.  It
>> is simply not worth doing.
>>
>> What would be worth doing, I think, is to keep a track of A % p for p in
>> the first n primes.  As you run through the A's, adding 2 to A each
>> step, you add 2 to each of these remainders in your tracking array.  If
>> these hit 0 (modulo their prime), then A is clearly non-prime and you
>> can skip it.  This will let you skip a number of your test divisions
>> with relatively little work - as you make that array of n primes bigger,
>> you cut out yet more divisions.  However, there is going to be a point
>> where doing this tracking for the modulo A % p will cost more (in memory
>> or speed) than 1/p times the cost of calculating C % A - and when you
>> reach that, you don't want to track any more modulos.
>>
>> I suspect there is scope for some interesting data structures to hold
>> this list of modulos, rather than a simple array - perhaps a priority
>> queue in a Fibonacci heap?
> 
> 
> Yes, this is the "standard" algorithm I was talking about, in the last
> post I even mentioned the heuristic you described it the third
> paragraph.
> Are you sure you wanted to post it as the answer to my post?
> 

That's not how I understood your post.  Though I agree the basic
algorithm is the same, the details are very different.  In particular,
your third paragraph suggested Miller-Rabin testing before division,
which I think would be terribly inefficient.

[toc] | [prev] | [next] | [standalone]

#5723

On 02.09.2015 16:37, David Brown wrote:
> On 02/09/15 16:27, bartekltg wrote:
>> On 02.09.2015 15:47, David Brown wrote:
>>> On 02/09/15 14:56, bartekltg wrote:
>>>> On 02.09.2015 14:19, Richard Heathfield wrote:
>>>>> On 02/09/2015 13:12, David Brown wrote:
>>>>>>
>>>>> <snip>
>>>>>>
>>>>>> There are a number of ways of doing this check faster than the
>>>>>> bit-for-bit long division you suggested elsewhere,
>>>>>
>>>>> The advantage of that way is that it's easy to explain, and relatively
>>>>> easy to implement. Having said that, I *haven't* implemented it (in
>>>>> software). My bignum library uses Algorithm D, from TAOCP II.
>>>>
>>>> I think explain something by using wrong algorithm can hurt
>>>> someone who think, so propably everyone who is listening to
>>>> 'how to factorize an integer;-)'
>>>>
>>>> But we can resurect this idea.
>>>>
>>>> Table of all n-digits prime can be too big for the universe,
>>>> so we have to generate it. One ot the simplest method is
>>>> to implement 'nextprime' - function that get the next odd*)
>>>> number and run fast primality test (Miller-Rabin),
>>>> repeat it until the number is pseudoprime.
>>>>
>>>
>>> The principle here is that to find the factors of C, we run through all
>>> primes A up to sqrt(C), and test if C % A == 0.  (It may be that there
>>> are other faster algorithms, but I don't know of any.)  If you know for
>>> sure the number of digits in A, then you could start 10^(noOfDigits-1),
>>> but that would only save 10% of the test time.
>>>
>>> Testing for the primality of each A is going to take a great deal more
>>> time than simply trying C % A == 0, even with a probable prime test.  It
>>> is simply not worth doing.
>>>
>>> What would be worth doing, I think, is to keep a track of A % p for p in
>>> the first n primes.  As you run through the A's, adding 2 to A each
>>> step, you add 2 to each of these remainders in your tracking array.  If
>>> these hit 0 (modulo their prime), then A is clearly non-prime and you
>>> can skip it.  This will let you skip a number of your test divisions
>>> with relatively little work - as you make that array of n primes bigger,
>>> you cut out yet more divisions.  However, there is going to be a point
>>> where doing this tracking for the modulo A % p will cost more (in memory
>>> or speed) than 1/p times the cost of calculating C % A - and when you
>>> reach that, you don't want to track any more modulos.
>>>
>>> I suspect there is scope for some interesting data structures to hold
>>> this list of modulos, rather than a simple array - perhaps a priority
>>> queue in a Fibonacci heap?
>>
>>
>> Yes, this is the "standard" algorithm I was talking about, in the last
>> post I even mentioned the heuristic you described it the third
>> paragraph.
>> Are you sure you wanted to post it as the answer to my post?
>>
>
> That's not how I understood your post.  Though I agree the basic
> algorithm is the same, the details are very different.  In particular,

I did not describe the 'standard' algorithm but explore Richarsd's/fir's
idea about an algorithm without divisions, but writt also without
checking all pairs.

> your third paragraph suggested Miller-Rabin testing before division,
> which I think would be terribly inefficient.

Yes, you are right, we do not have to check if A is (pseudo)prime,
and in reality, like you said, M-R test is slower than division.

This was written that way to resemble 'check all pair',
but yes, it was stupid idea;-)

bartekltg

[toc] | [prev] | [next] | [standalone]

#5785

On 02/09/15 17:01, bartekltg wrote:
> On 02.09.2015 16:37, David Brown wrote:
>> On 02/09/15 16:27, bartekltg wrote:
>>> On 02.09.2015 15:47, David Brown wrote:
>>>> On 02/09/15 14:56, bartekltg wrote:
>>>>> On 02.09.2015 14:19, Richard Heathfield wrote:
>>>>>> On 02/09/2015 13:12, David Brown wrote:
>>>>>>>
>>>>>> <snip>
>>>>>>>
>>>>>>> There are a number of ways of doing this check faster than the
>>>>>>> bit-for-bit long division you suggested elsewhere,
>>>>>>
>>>>>> The advantage of that way is that it's easy to explain, and
>>>>>> relatively
>>>>>> easy to implement. Having said that, I *haven't* implemented it (in
>>>>>> software). My bignum library uses Algorithm D, from TAOCP II.
>>>>>
>>>>> I think explain something by using wrong algorithm can hurt
>>>>> someone who think, so propably everyone who is listening to
>>>>> 'how to factorize an integer;-)'
>>>>>
>>>>> But we can resurect this idea.
>>>>>
>>>>> Table of all n-digits prime can be too big for the universe,
>>>>> so we have to generate it. One ot the simplest method is
>>>>> to implement 'nextprime' - function that get the next odd*)
>>>>> number and run fast primality test (Miller-Rabin),
>>>>> repeat it until the number is pseudoprime.
>>>>>
>>>>
>>>> The principle here is that to find the factors of C, we run through all
>>>> primes A up to sqrt(C), and test if C % A == 0.  (It may be that there
>>>> are other faster algorithms, but I don't know of any.)  If you know for
>>>> sure the number of digits in A, then you could start 10^(noOfDigits-1),
>>>> but that would only save 10% of the test time.
>>>>
>>>> Testing for the primality of each A is going to take a great deal more
>>>> time than simply trying C % A == 0, even with a probable prime
>>>> test.  It
>>>> is simply not worth doing.
>>>>
>>>> What would be worth doing, I think, is to keep a track of A % p for
>>>> p in
>>>> the first n primes.  As you run through the A's, adding 2 to A each
>>>> step, you add 2 to each of these remainders in your tracking array.  If
>>>> these hit 0 (modulo their prime), then A is clearly non-prime and you
>>>> can skip it.  This will let you skip a number of your test divisions
>>>> with relatively little work - as you make that array of n primes
>>>> bigger,
>>>> you cut out yet more divisions.  However, there is going to be a point
>>>> where doing this tracking for the modulo A % p will cost more (in
>>>> memory
>>>> or speed) than 1/p times the cost of calculating C % A - and when you
>>>> reach that, you don't want to track any more modulos.
>>>>
>>>> I suspect there is scope for some interesting data structures to hold
>>>> this list of modulos, rather than a simple array - perhaps a priority
>>>> queue in a Fibonacci heap?
>>>
>>>
>>> Yes, this is the "standard" algorithm I was talking about, in the last
>>> post I even mentioned the heuristic you described it the third
>>> paragraph.
>>> Are you sure you wanted to post it as the answer to my post?
>>>
>>
>> That's not how I understood your post.  Though I agree the basic
>> algorithm is the same, the details are very different.  In particular,
> 
> I did not describe the 'standard' algorithm but explore Richarsd's/fir's
> idea about an algorithm without divisions, but writt also without
> checking all pairs.
> 
>> your third paragraph suggested Miller-Rabin testing before division,
>> which I think would be terribly inefficient.
> 
> Yes, you are right, we do not have to check if A is (pseudo)prime,
> and in reality, like you said, M-R test is slower than division.
> 
> This was written that way to resemble 'check all pair',
> but yes, it was stupid idea;-)
> 
> bartekltg
> 

There have been a variety of silly ideas in this thread (some
intentional, some accidental), as well as some good ones.

But no one has come up with a working idea that actually has a chance of
factoring a 600 digit number!

[toc] | [prev] | [next] | [standalone]

#5786

On 03/09/2015 09:55, David Brown wrote:
> On 02/09/15 17:01, bartekltg wrote:

<snip>

> There have been a variety of silly ideas in this thread (some
> intentional, some accidental), as well as some good ones.
>
> But no one has come up with a working idea that actually has a chance of
> factoring a 600 digit number!

I have every confidence that I can factor the 602-digit integer I posted 
upthread, in considerably less than a short while. I might even be 
prepared to bet a very large sum of money on it.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5787

On 03/09/15 11:05, Richard Heathfield wrote:
> On 03/09/2015 09:55, David Brown wrote:
>> On 02/09/15 17:01, bartekltg wrote:
> 
> <snip>
> 
>> There have been a variety of silly ideas in this thread (some
>> intentional, some accidental), as well as some good ones.
>>
>> But no one has come up with a working idea that actually has a chance of
>> factoring a 600 digit number!
> 
> I have every confidence that I can factor the 602-digit integer I posted
> upthread, in considerably less than a short while. I might even be
> prepared to bet a very large sum of money on it.
> 

Good point!

I have every confidence that I too could factor it, if you give me your
home address - if all else fails, rubber hose cryptoanalysis is almost
always successful :-)

[toc] | [prev] | [next] | [standalone]

#5788

On 03/09/2015 10:49, David Brown wrote:
> On 03/09/15 11:05, Richard Heathfield wrote:
>>  On 03/09/2015 09:55, David Brown wrote:
>>>  On 02/09/15 17:01, bartekltg wrote:
>>
>>  <snip>
>>
>>>  There have been a variety of silly ideas in this thread (some
>>>  intentional, some accidental), as well as some good ones.
>>>
>>>  But no one has come up with a working idea that actually has a chance of
>>>  factoring a 600 digit number!
>>
>>  I have every confidence that I can factor the 602-digit integer I posted
>>  upthread, in considerably less than a short while. I might even be
>>  prepared to bet a very large sum of money on it.
>>
>
> Good point!
>
> I have every confidence that I too could factor it, if you give me your
> home address

No problem. It's 127.0.0.1

>  - if all else fails, rubber hose cryptoanalysis is almost
> always successful :-)

Thanks for the heads-up. I'll lock the shed.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5789

On 03/09/15 11:54, Richard Heathfield wrote:
> On 03/09/2015 10:49, David Brown wrote:
>> On 03/09/15 11:05, Richard Heathfield wrote:
>>>  On 03/09/2015 09:55, David Brown wrote:
>>>>  On 02/09/15 17:01, bartekltg wrote:
>>>
>>>  <snip>
>>>
>>>>  There have been a variety of silly ideas in this thread (some
>>>>  intentional, some accidental), as well as some good ones.
>>>>
>>>>  But no one has come up with a working idea that actually has a
>>>> chance of
>>>>  factoring a 600 digit number!
>>>
>>>  I have every confidence that I can factor the 602-digit integer I
>>> posted
>>>  upthread, in considerably less than a short while. I might even be
>>>  prepared to bet a very large sum of money on it.
>>>
>>
>> Good point!
>>
>> I have every confidence that I too could factor it, if you give me your
>> home address
> 
> No problem. It's 127.0.0.1
> 
>>  - if all else fails, rubber hose cryptoanalysis is almost
>> always successful :-)
> 
> Thanks for the heads-up. I'll lock the shed.
> 

There is a more serious point to all this - sometimes you don't actually
want your encryption system to be impossible to break.  If you have
something really worthwhile to hide, to the extent that you fear it will
be of interest to the Russian Mafia, the NSA, or other criminal
networks, then you want it to be cheaper and easier for them to buy a
supercomputer or rent a botnet than for them to find ways to "persuade"
you to give them the secret keys.

[toc] | [prev] | [next] | [standalone]

#5790

On 03.09.2015 10:55, David Brown wrote:
> There have been a variety of silly ideas in this thread (some
> intentional, some accidental), as well as some good ones.
>
> But no one has come up with a working idea that actually has a chance of
> factoring a 600 digit number!

No one in this thread has also idea how to solve Goldbach conjecture,
whether P==NP or not, and how to solve world hunger.

Half of the cryptography systems is based on assumption a bunch
of programmers on usenet group cant solve it i a week.

;-)

BTW, I was hoping that Richard used two too similar prime numbers
and I ran very simple version of Fermat's factorization method,
but he was more clever;>

As we speak about security in cryptography, this would be a huge
mistake.

Look at this number:

N=6656306008655249164123957612534222424912000368941290054361681671810\
473358156447838705173390562626790029530951700110242362363665522412966\
725184603920088147004248502697963491242610310414234911578383282256458\
276766370874401860439165075488781472945530061660501484047480394326484\
617103517504379135200662278550486571819968410075879270762270920098859\
240729081188660838597729331149890859253931757548325818599364031204421\
156056681989351055481408743375643625566195491880462272863893726745649\
214127868608491830095813911837740111440280522968022277001255214954922\
415509187661120404292711047616795049622143667025617

a=ceil(sqrt(N)) is an integer

b2 = a*a-N = 2549038144 = 50488^2.

So
N = a^2 - b^2 = (a-b)(a+b)
We have factorization!

(a-b)
257998178455880753222629957810224903188635668669054943523104315214939\
729141587689643443680630721865791158466117549986755369945232060506699\
900127884744200089328505770486767278922047555842792645845125657099338\
127228378237306269322260898614453779605444120709703492181445013380135\
0709313944644504923750193
(a+b)
257998178455880753222629957810224903188635668669054943523104315214939\
729141587689643443680630721865791158466117549986755369945232060506699\
900127884744200089328505770486767278922047555842792645845125657099338\
127228378237306269322260898614453779605444120709703492181445013380135\
0709313944644504923851169

For
1167828229045445971662249118780447846520421784147226620494055391458180\
7601997478699930291352869903692219072218113241990374766447439973877729\
4941194722252835014243689673136787968254216972130137233976876436369535\
2457619346774027074180718388851030931546938988468043490672744425493977\
4094716263320750073186079507225495976235748036343558057410341532576049\
9174965884053070606699130271736508915807365053190141312702103604293220\
0884758543647787591759476041043940010480149898083866228838017408185691\
0653989137800961071176307478195531410877286659821988923600607842238369\
4669208917896312708803930694693988566589

a=ceil(sqrt(N))
b2 = a*a-N is not an perfect square, but if one check a couple bigger 
values - a=ceil(sqrt(N))+36 works.

p2-p1 was ~10^151, so only a half of booth numbers is the same

p1
34173501855172027009217658731049403512738189648854815841795142373676940621\
91652926400102176450757018262769049636027036800905264842784680568455612306\
69669953975946543695876440518626912368990108659170659267659700340363124255\
302847431247260784486932195413513794132970440858067868458027521763718757288441
p2
34173501855172027009217658731049403512738189648854815841795142373676940621\
91652926400102176450757018262769049636027036800905264842784680568455612306\
79669953975946543695876440518626912368990108659170659267659700340363124255\
302847431247260784486932195413513794132970440858067868458027521763718757289829



bartekltg

[toc] | [prev] | [next] | [standalone]

#5714

[Sorry for second reply to same article - an afterthought occurs]

On 02/09/2015 13:12, David Brown wrote:

<snip>

> You were also inspired by the wording of Fir's suggested algorithm - as
> far as I can see, he did want to factor C by trying combinations of A *
> B, and thus your calculations for the number of tests needed were correct.

In firness to fair, or rather in fairness to fir, he did write, quite 
early on in the thread:

"or instead of checking many A*B only divisions C/A == B could be checked"

Seeing A and B in there was what threw me, I think. What he should have 
written was: C % A = 0. Then all would have been clear, or at least 
clearer. But he was on the right track for a change, and I wasn't.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#5680

On Mon, 31 Aug 2015 12:07:52 -0700 (PDT), fir <profesor.fir@gmail.com>
wrote:

>I heard (read some) thet if one will take two large primes A, B (like 300 digits or so) and multiply them to C (will probably get 600 digit number) - then will gave some task to de-factorise C on A and B then it is today impossible task - used in cryptography
>
>really it is so hard? maybe it is but isnt then a proces of finding those 300-digit primes also hard? is it possible to find A and B (which need much more test as all factors must be checked) but this is harder to make a lot of simple multiplies scanning 
>some propositions? (as C lenght is given
>for given a some B could be like deduced - or instead of checking many A*B only divisions C/A == B could be checked..
>
>whats with that


A good place to start reading:

https://en.wikipedia.org/wiki/Integer_factorization

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.programming

csiph-web