mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Homework Help

Reply
 
Thread Tools
Old 2022-06-09, 14:43   #1
Ombrah
 
Jun 2022

22 Posts
Default 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
Ombrah is offline   Reply With Quote
Old 2022-06-09, 15:38   #2
chris2be8
 
chris2be8's Avatar
 
Sep 2009

23·103 Posts
Default

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).
chris2be8 is offline   Reply With Quote
Old 2022-06-09, 16:00   #3
Ombrah
 
Jun 2022

22 Posts
Default

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.
Ombrah is offline   Reply With Quote
Old 2022-06-09, 16:38   #4
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

150D16 Posts
Default

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.
VBCurtis is offline   Reply With Quote
Old 2022-06-09, 16:57   #5
Ombrah
 
Jun 2022

48 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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?
Ombrah is offline   Reply With Quote
Old 2022-06-09, 19:31   #6
mathwiz
 
Mar 2019

12716 Posts
Default

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 = <your semiprime>
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!
mathwiz is online now   Reply With Quote
Old 2022-06-09, 20:39   #7
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·3·379 Posts
Default

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
a1call is offline   Reply With Quote
Old 2022-06-10, 00:35   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×1,063 Posts
Default

How about gcd(P*Q, p1.p2.p3...p100)? (All primes)
paulunderwood is offline   Reply With Quote
Old 2022-06-10, 00:45   #9
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·3·379 Posts
Default

That would work if only one of the 2 primes is in the list of all primes.
a1call is offline   Reply With Quote
Old 2022-06-10, 02:24   #10
Ombrah
 
Jun 2022

48 Posts
Thumbs up

Thank you. I will look into coding it with Python or one of the others you guys recommended.
Ombrah is offline   Reply With Quote
Old 2022-06-10, 05:38   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

2·3·379 Posts
Default

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.
a1call is offline   Reply With Quote
Reply

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 2017-10-29 01:31
Manual testing on CPU list Fred PrimeNet 3 2016-02-12 02:49
Time needed to factor a 150 digit number ladderbook Factoring 14 2008-11-27 13:02
Is it time for a 100M digit option? petrw1 PrimeNet 60 2008-09-30 22:43
50 Digit Testing wblipp ElevenSmooth 1 2003-11-15 23:53

All times are UTC. The time now is 14:19.


Thu Aug 18 14:19:01 UTC 2022 up 11:47, 0 users, load averages: 1.36, 1.37, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔