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-09, 14:43 #1 Ombrah   Jun 2022 416 Posts Testing a list of 65-digit primes instead of one at a time Greetings, I am working on factoring a 130-digit semiprime (comprised of two 65-digit primes) and would like to check more than one 65-digit prime at a time. Is there a program that allows for checking a list of maybe five to ten 65-digit primes at a time? Thank you. -Ombrah
 2022-06-09, 15:38 #2 chris2be8     Sep 2009 94016 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 CADO-NFS 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).
 2022-06-09, 16:00 #3 Ombrah   Jun 2022 22 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.
 2022-06-09, 16:38 #4 VBCurtis     "Curtis" Feb 2005 Riverside, CA 150116 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 factor-checker that is the challenge she has given you.
2022-06-09, 16:57   #5
Ombrah

Jun 2022

22 Posts

Quote:
 Originally Posted by VBCurtis 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 factor-checker that is the challenge she has given you.
So, how do I feed a list into a factor-checker?

 2022-06-09, 19:31 #6 mathwiz   Mar 2019 22·73 Posts Okay. So your setup is: 1. You have a 130-digit semiprime, and 2. You are given a list of a hundred 65-digit 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 = primes = [2, 3, 5, 7, ...] <-- note: replace with primes you are given for p in primes: if N % p == 0: print(p) There's no need to check more than one at a time, as this code should run in well under a second on a modern machine. 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!
 2022-06-09, 20:39 #7 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 1000110110102 Posts Although it is highly recommended that you learn to use Programming/Scripting codes (PARI-GP is easy enough for me to use ), there is a Low-tech alternative that you can try. If you are certain that both prime factors of the semiprime are present in the list of 100 randomly-distributed 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 2022-06-09 at 20:40
 2022-06-10, 00:35 #8 paulunderwood     Sep 2002 Database er0rr 109C16 Posts How about gcd(P*Q, p1.p2.p3...p100)? (All primes)
 2022-06-10, 00:45 #9 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2×11×103 Posts That would work if only one of the 2 primes is in the list of all primes.
 2022-06-10, 02:24 #10 Ombrah   Jun 2022 410 Posts Thank you. I will look into coding it with Python or one of the others you guys recommended.
 2022-06-10, 05:38 #11 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 2·11·103 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.

 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 00:46.

Sat Aug 13 00:46:44 UTC 2022 up 36 days, 19:34, 2 users, load averages: 1.53, 1.15, 1.13