Browse Groups

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

(8)
• NextPrevious
• ... 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
View Source
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 1 of 8 , Jul 13, 2004
View Source
>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 1 of 8 , Jul 14, 2004
View Source
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 1 of 8 , Jul 14, 2004
View Source
<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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.