Testing a list of 65-digit primes instead of one at a time

[Ombrah]

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

[chris2be8]

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).

[Ombrah]

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.

[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.

[Ombrah]

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?

[mathwiz]

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:

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!

[a1call]

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.

[paulunderwood]

How about gcd(P*Q, p1.p2.p3...p100)? (All primes)

[a1call]

That would work if only one of the 2 primes is in the list of all primes.

[Ombrah]

Thank you. I will look into coding it with Python or one of the others you guys recommended.

[a1call]

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.