160 digit factor found of 366 digit (PRP-1)

[AntonVrba]

I am trying to prove the following number prime
p=(2^607-1)*(2^607-169662)+169661

p-1 has following prime factors
2
3 ^ 4
7 ^ 2
13
607
2663
117210 040608 611501
and 160 digit composite factor:
2077 722215 701465 989903 905378 105865 831121
690269 515432 941764 890410 612443 142155 675750
703708 696614 154976 284846 472630 448131 063469
226632 172413 531787 662918 734708 751011
and a remaining 178 digit composite factor

Is finding a 160 digit composite factor a noteworthy record?

Congratulations to Dario Alpern's http://www.alpertron.com.ar/ECM.HTM

The Java applet is now stuck on the 160 digit factor so I installed ecm-6.0.1. Any pointers for the best command line - never used ecm before.


regards
Anton

[akruppa]

Not if it is an algebraic factor - which it undoubtedly is. Before continuing with ECM, try to find all algebraic factors of your number. It will make your job very much easier.

Alex

[R.D. Silverman]

Originally Posted by AntonVrba

I am trying to prove the following number prime
p=(2^607-1)*(2^607-169662)+169661

p-1 has following prime factors
2
3 ^ 4
7 ^ 2
13
607
2663
117210 040608 611501
and 160 digit composite factor:
2077 722215 701465 989903 905378 105865 831121
690269 515432 941764 890410 612443 142155 675750
703708 696614 154976 284846 472630 448131 063469
226632 172413 531787 662918 734708 751011
and a remaining 178 digit composite factor

Is finding a 160 digit composite factor a noteworthy record?

Congratulations to Dario Alpern's http://www.alpertron.com.ar/ECM.HTM

The Java applet is now stuck on the 160 digit factor so I installed ecm-6.0.1. Any pointers for the best command line - never used ecm before.


regards
Anton

You are trying to kill an ant with a sledgehammer.

ECPP or Cyclotomy methods will prove this prime (if it is) in just a few minutes. Why waste factoring a 160-digit composite?

[John Renze]

Originally Posted by R.D. Silverman

ECPP or Cyclotomy methods will prove this prime (if it is) in just a few minutes.

For the record:

(2^607 - 1)*(2^607 - 169662) + 169661 - 1 == 2(2^303 - 1)(2^303 + 1)(2^607 - 169661)

The algebraic factors 2^303-1 and 2^303+1 have each been completely factored, as revealed by quick check of the Cunningham project tables. This is enough for a classical proof, so you don't even have to bother with 2^607-169661.

The algebraic factorization is not a coincidence. How did you choose to study this form?

John

[akruppa]

Thanks for the factorisation, John.

2^607 - 169661 is a fairly easy SNFS number. Anton, you probably won't need this factored any more for your proof, but if want it done, let me know.

Alex

[AntonVrba]

Originally Posted by akruppa

Thanks for the factorisation, John.

2^607 - 169661 is a fairly easy SNFS number. Anton, you probably won't need this factored any more for your proof, but if want it done, let me know.

Alex

Thanks all

BTW, Marcel Martin's Primo has done the job of prooving p=(2^607-1)*(2^607-169662)+169661 prime

regards
Anton

[alpertron]

My applet also declares that the original number is prime by using the APRT-CLE algorithm. So no external programs were needed in this case to prove primality.

Notice that the applet cracked p-1 by using Lehman factorization. This is because it is a product of two similar numbers.

[alpertron]

If you had entered ((2^607 - 1)*(2^607 - 169662) + 169661 - 1)/2/(2^607 - 169661) in the upper box the applet would have completed the factorization. This is because it search in the Web server known factorizations of Cunningham numbers.