## Re: [PrimeNumbers] RE:[Factoring large numbers

Expand Messages
• ... In that case, it is almost certainly too hard to factor with present-day hardware and software. The values of a and b ma just be such that a
Message 1 of 8 , Jul 13, 2004
On Tue, 2004-07-13 at 09:20, cino hilliard wrote:

> The pari program below produces primes. I produced primes for
> digitsqrpr(2000,m,150) and digitsqrpr(2000,m,200) and randomly selected a
> prime from each a,b
> output and multiplied them. I forgot what m I used or if it was the same for
> both or different as
> I did p = a*b and a prime() and then factor(p) and had to abort the
> session. I had copied p earlier
> to text to test for primality with another program which worked faster tham
> Pari. all I know is
> a is <= 150 digits and b is <=200 digits.

In that case, it is almost certainly too hard to factor with present-day
hardware and software. The values of a and b ma just be such that a
special-purpose algorithm such as P-1 may find them but the odds are
very much against it.

Almost certainly the easiest way to find the factors would be to
reverse-engineer the pseudorandom procedure used to generate the primes
in the first place.

Paul
• ... I did this and found the org number was copied and pasted wrong and was easy to factor as was pointed out by other posters. I did not set the limit in
Message 2 of 8 , Jul 13, 2004
>From: Paul Leyland <pcl@...>
>To: cino hilliard <hillcino368@...>
>Subject: Re: [PrimeNumbers] RE:[Factoring large numbers
>Date: 13 Jul 2004 10:38:32 +0100
>
>On Tue, 2004-07-13 at 09:20, cino hilliard wrote:
>
> > Pari. all I know is
> > a is <= 150 digits and b is <=200 digits.
>
>In that case, it is almost certainly too hard to factor with present-day
>hardware and software. The values of a and b ma just be such that a
>special-purpose algorithm such as P-1 may find them but the odds are
>very much against it.
>
>Almost certainly the easiest way to find the factors would be to
>reverse-engineer the pseudorandom procedure used to generate the primes
>in the first place.
>
I did this and found the org number was copied and pasted wrong and was easy
to factor as was
pointed out by other posters. I did not set the limit in factor(n,{lim}) in
pari. Doing this
(14:56) gp > factor(p,1000)
time = 0 ms.
%25 =
[13 1]

[199 1]

[263 1]

[379 1]

[678026493414538148553665596445813830734630833053024846216579340872093413327647
4762803097949211213281819670661292330131124527435326156088028931580262368994401
6643351267973947046046313935094275418438526691021308861240797797863806746646690
8508141216855178178499487049221885287729920843955819202763969676507087051775192
055290647644770812521271 1]

So this mistake finds yet another large factor! I will play the lotto from
this list. :-)

The correct number I should have posted is

1220516103632118734239552093546852845556567859549464947942804246975191952318939
5382087627014892247240874902346477975756822244476470920475366468143120795553304
9000712508365396500993156592586695125254256067267320061792206044621345381741861
7266932089747110235311534348244823636951507811274424010127339017948672442184669
1782447097625239591063539221131129

One poster claims to factor 150,000 digit numbers. Here is a 350 digit
number. I do not see it any
different than the RSA challenges in this category. We will see.

So far, I and only I know the two factors. Gee, I don't know if I can handle
that much power :-)

Have fun,
CLH
• I have been curious about trying to factor large numbers and on public computers (my home computer is FAR too old!) I have not been able to factor any number
Message 3 of 8 , Jul 14, 2004
I have been curious about trying to factor large numbers and on public
computers (my home computer is FAR too old!) I have not been able to
factor any number with more than 50 digits, whilst modern software can
usually find factors up to 40 or 45 digits (I found this when I saw how
dismal the prospects for fully factoring F12 [2^4096+1] in the near
future really are).

What sort of number would this new factoring method work upon? If it
could only work on a 150 digit number, it would be of little use for
factoring such numbers as Cunningham numbers.
• ... digit ... Try running a few ECM curves on F20 (20th Fermat Number) and you ll be attempting to factor a 315,653 digit number. Factoring of 150k digit
Message 4 of 8 , Jul 14, 2004
<hillcino368@h...> wrote:
>
> One poster claims to factor 150,000 digit numbers. Here is a 350
digit
> number. I do not see it any
> different than the RSA challenges in this category. We will see.

Try running a few ECM curves on F20 (20th Fermat Number) and you'll
be attempting to factor a 315,653 digit number. Factoring of 150k
digit numbers is nothing new in the 21st Century. :)

As to the RSA comparison... When you're willing to put up \$20k in
prize money, I suspect you'll get people trying to factor your
number. But if you do, make certain to post a reasonable challenge
and/or a reasonable reward. The next RSA challenge (RSA-640, \$20k
prize) is only 193 digits with factors estimated at 85-88 digits.
While the RSA-1024 challenge is 309-digits with a \$100k prize. So I
figure you'll need about \$250k as a prize to get anyone to take your
challenge very seriously.
Your message has been successfully submitted and would be delivered to recipients shortly.