20220609, 14:43  #1 
Jun 2022
4_{16} Posts 
Testing a list of 65digit primes instead of one at a time
Greetings,
I am working on factoring a 130digit semiprime (comprised of two 65digit primes) and would like to check more than one 65digit prime at a time. Is there a program that allows for checking a list of maybe five to ten 65digit primes at a time? Thank you. Ombrah 
20220609, 15:38  #2 
Sep 2009
100101000001_{2} Posts 
Unless you know at least one of the factors comes from a fairly short list then trying 65 digit primes one or a few at a time is completely pointless. You would have to try more than 10^60 primes before finding a factor.
It would not be hard to factor with GNFS. Either GGNFS or CADONFS could do it in a day or so on a decent PC (though it'll take longer to work out how to use either of them). 
20220609, 16:00  #3 
Jun 2022
4_{8} Posts 
A really smart friend of mine said, "I'll give you 100 primes that it could be. How fast can you find it?"
She knows I don't know programming, so I'm just looking to save some time, and I want to learn some programming (though I'm not at her level). I'm a pretty simple guy. 
20220609, 16:38  #4 
"Curtis"
Feb 2005
Riverside, CA
2^{2}×3×449 Posts 
If there are only 100 to check, it doesn't matter whether a program checks 1 at a time or 10 at a time; either way, you'd have an answer in less than a second as to which it is.
The program itself would take nearly no time it's learning how to feed a list into a factorchecker that is the challenge she has given you. 
20220609, 16:57  #5  
Jun 2022
4_{16} Posts 
Quote:


20220609, 19:31  #6 
Mar 2019
5·59 Posts 
Okay. So your setup is:
1. You have a 130digit semiprime, and 2. You are given a list of a hundred 65digit primes, one of which, you are told, is the factor? If that's the case, you can use Python to do something like: Code:
N = <your semiprime> primes = [2, 3, 5, 7, ...] < note: replace with primes you are given for p in primes: if N % p == 0: print(p) Of course, you can accomplish the same thing in PARI/GP, or pretty much any other programming language; this is just an example. But you might want to try https://www.learnpython.org or CodeAcademy, etc. to learn some actual programming after this exercise! 
20220609, 20:39  #7 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,273 Posts 
Although it is highly recommended that you learn to use Programming/Scripting codes (PARIGP is easy enough for me to use ), there is a Lowtech alternative that you can try. If you are certain that both prime factors of the semiprime are present in the list of 100 randomlydistributed primes, You can use a scientific calculator (Windows has one) or even pen and paper to enter the semiprime in scientific notations and divide by each prime (in scientific notations) and see if the result matches any of the other remaining primes (accommodating for the lower digit uncertainties).
Just a thought. Please let us know how it goes. Last fiddled with by a1call on 20220609 at 20:40 
20220610, 00:35  #8 
Sep 2002
Database er0rr
2^{2}·1,063 Posts 
How about gcd(P*Q, p1.p2.p3...p100)? (All primes)

20220610, 00:45  #9 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,273 Posts 
That would work if only one of the 2 primes is in the list of all primes.

20220610, 02:24  #10 
Jun 2022
2^{2} Posts 
Thank you. I will look into coding it with Python or one of the others you guys recommended.

20220610, 05:38  #11 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2,273 Posts 
In keeping with the title of this thread, even if both primes are in the list you could pinpoint them using Paul’s method with systematic grouping of the primes and then performing the gcd which will give you the greatest common divisor.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
PRP double checks are also included in the first time list  retina  PrimeNet  6  20171029 01:31 
Manual testing on CPU list  Fred  PrimeNet  3  20160212 02:49 
Time needed to factor a 150 digit number  ladderbook  Factoring  14  20081127 13:02 
Is it time for a 100M digit option?  petrw1  PrimeNet  60  20080930 22:43 
50 Digit Testing  wblipp  ElevenSmooth  1  20031115 23:53 