mersenneforum.org Testing a list of 65-digit primes instead of one at a time
 Register FAQ Search Today's Posts Mark Forums Read

2022-06-10, 14:07   #23
Dr Sardonicus

Feb 2017
Nowhere

2×5×11×53 Posts

Quote:
 Originally Posted by xilman Arjen Lenstra et al. did something closely similar to this exercise a few years back. They collected a very large number of RSA public moduli and found common factors within the set, thereby breaking a large number of live public keys. I will see if I can find the paper ... here it is https://eprint.iacr.org/2012/064 https://souravsengupta.com/publications/2017_iciss.pdf indicates that the algorithm can be parallelized.

 2022-06-14, 13:10 #24 ThiloHarich     Nov 2005 10410 Posts Daniel Bernstein covered this Problem in the Remainder- and Product Trees: https://cr.yp.to/arith/scaledmod-20040820.pdf Using Fast (n*log(n)) Multiplications, you can find the gcd of a number and some other numbers (possible divisors) fast, by using a tree. This can also be used in the Quadratic Sieve.
 2022-06-18, 06:14 #25 MattcAnderson     "Matthew Anderson" Dec 2010 Oregon, USA 22×3×5×19 Posts see post number 12 from kar_bon. That is a good post. Easy solution to OP's request. That is all. Matt Have a nice day.

 Similar Threads Thread Thread Starter Forum Replies Last Post retina PrimeNet 6 2017-10-29 01:31 Fred PrimeNet 3 2016-02-12 02:49 ladderbook Factoring 14 2008-11-27 13:02 petrw1 PrimeNet 60 2008-09-30 22:43 wblipp ElevenSmooth 1 2003-11-15 23:53

All times are UTC. The time now is 12:43.

Thu Jun 30 12:43:01 UTC 2022 up 77 days, 10:44, 0 users, load averages: 1.57, 1.44, 1.59