4

I have a homework assignment to find the two smallest probable primes with $12$ digits, where a probable prime is defined as a number such that $a^{p-1} \equiv 1\ (\textrm{mod}\ p)$, where $a = 2, 3, 5, 7$.

I'm obviously not asking for this to be done for me, but I'm having trouble figuring out a way to do anything other than to brute-force it by checking each of the four congruences for each (odd) $12$ digit number $n$ until I find two of them.

Can someone offer me some hint, relevant theorem, or something that I might be able to use to figure out how to do find these numbers in a more efficient manner? Thanks for any help.

Michael Albanese
  • 99,526
Nate
  • 63
  • 4
    Are you sure you aren't supposed to just brute-force it? (It's not too bad; binary exponentiation should be really fast for numbers this small and you only have to check numbers which aren't divisible by 2, 3, 5, or 7.) – Qiaochu Yuan Oct 12 '10 at 22:02
  • Well, I tried to brute force it but after 12 hours it didn't find anything. Perhaps the problem is that my code is just inefficient (i'm quite the amateur when it comes to programming). I'll try and optimize and report back. Thanks for the input =) – Nate Oct 12 '10 at 22:11
  • After that much time, you might check for a bug by using few enough digits that you can find some numbers another way that you know are prime. See if your code finds them. – Ross Millikan Oct 12 '10 at 22:15
  • Obviously the next 2 primes will work, so you don't need to test many candidates. Are you doing the modular exponentiation quickly by repeated squaring? – Bill Dubuque Oct 12 '10 at 22:43
  • Also that there is a prime between $n$ and $2n$ (Bertrand's postulate) you have a finite search space. –  Oct 12 '10 at 22:53
  • I might have been unclear in what i was looking for. I'm not searching for prime numbers, i'm searching for numbers p that satisfy:

    a^(p-1) = 1 (mod p) , for a=2,3,5,7

    these are called 'probable primes' and might not necessarily be prime. I need the two smallest 12 digit ones, and brute forcing still isn't coming up with anything. I'm working through my code now, looking for bugs still.

     – Nate Oct 12 '10 at 23:49
  • Give us a link to your code and we might be able to help. I assume you're computing a^(p-1) using (((a^2)^2)^2) and so on, right (as someone else asked). –  Oct 13 '10 at 00:51
  • Okay, I didn't really understand what you guys meant about using binary exponentiation before, but i finally realized what you guys are talking about and i see how that could drastically speed up what i'm trying to do, I'm just failing at implementing it. It's not even worth posting my code because what I have is too embarassing at this point, but thanks for offering to help. I can't help but think there must be a way other than brute force to do this, because i'm in a class that doesn't assume any real level of programming competence... – Nate Oct 13 '10 at 01:43
  • Depending upon your language, Python has a function pow(a,b,c) that gives $a^b (mod c)$ much more efficiently than you can do yourself. I suspect others do, as well. And I hope you are doing $a^{(p-1)}=1 (mod p) – Ross Millikan Oct 13 '10 at 01:59
  • 1
    Thanks for the help guys.My attempts to write a function to do binary modular exponentiation by repeated squaring did not turn out well. Luckily, I found a C# library that could handle very big integers and had already implemented modular exponentiation ( http://www.codeproject.com/KB/cs/BigInteger_Library.aspx?artkw=C ) so i used that and got my answers very quickly... 100000000003 and 100000000019.

    Ross - yes, that's what i was trying to do. Thanks for the python suggestion, I'll use it if i ever need to do any more number theory that relies on efficiently doing exponentiation.

     – Nate Oct 13 '10 at 02:31
  • I saw on http://primes.utm.edu/prove/prove2_3.html If n < 25,000,000,000 is a 2, 3, 5 and 7-SPRP, then either n = 3,215,031,751 or n is prime [PSW80]. (This is actually true for n < 118,670,087,467 [Jaeschke93].) So numbers that pass the test for 2,3,5,7 are pretty rare. Unless your teacher picked the base carefully, the primes and pseudoprimes are the same. – Ross Millikan Oct 13 '10 at 03:56
  • 1
    @Ross Millikan: The OP is doing a weaker Fermat PRP test, not an SPRP test, so the SPRP results that you quote do not apply here. – Bill Dubuque Oct 13 '10 at 19:42
  • @Nate: Yes, I know you are looking for probable primes. But primes are probable primes. In fact both integers in the answer that you seek are in fact prime and, as I said, you don't have to search very far to find them. – Bill Dubuque Oct 13 '10 at 19:46
  • @Bill Dubuque: indeed, once i figured out what i was doing wrong I realized the relevance of what you were saying. Sorry about the confusion, I appreciate the help. – Nate Oct 13 '10 at 21:18

1 Answers1

2

Since you already found your answers, I'll go ahead an post a solution. I find that python is a much better choice for problems like yours where you need large integer support (it's built in!) and where you don't have a lot of computation (python is slow, in general). This is all you need to do modular exponentiation with repeated squaring:

def modx(base,exp,mod):
    r = 1;
    while (exp > 0):
        if (exp % 2 == 1):
            r = (r * base) % mod
        base = (base * base) % mod
        exp = exp/2
    return r

Now another small function to test for your "probable prime" condition:

def probprime(s):
    while (modx(2,s-1,s) != 1  or  modx(3,s-1,s) != 1  or modx(5,s-1,s) != 1 or modx(7,s-1,s) != 1):
        s += 1
    return(s)

And you're done! Run python, input the two functions above and type:

>>> probprime(10**11)
100000000003
>>> probprime(probprime(10**11)+1)
100000000019

...which matches your answers.

Fixee
  • 11,565