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.

  • 3
    $\begingroup$ 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.) $\endgroup$ – Qiaochu Yuan Oct 12 '10 at 22:02
  • $\begingroup$ 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 =) $\endgroup$ – Nate Oct 12 '10 at 22:11
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Oct 12 '10 at 22:15
  • $\begingroup$ 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? $\endgroup$ – Bill Dubuque Oct 12 '10 at 22:43
  • 1
    $\begingroup$ 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 ( 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. $\endgroup$ – Nate Oct 13 '10 at 2:31

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

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

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

...which matches your answers.

  • 2
    $\begingroup$ You don't even have to write modx, it is built in. $\endgroup$ – Ross Millikan Oct 21 '12 at 16:10
  • 1
    $\begingroup$ @RossMillikan True, to be more direct, it's the built-in pow(Python2, Python 3) with three arguments. I strongly recommend using it instead of the above (very limited) modx implementation. $\endgroup$ – Wolf Feb 18 '15 at 14:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.