Playing around with modular arithmetic

[jemidiah]

I was reading Wikipedia's page on Wilson's Theorem and thought a few people might enjoy fiddling with some of the underlying ideas on a computer. Here are a few leading questions.


1) Pick a prime number p, multiply the numbers 1, 2, ..., p-1, and take the result mod p. How does the result depend on p? [Computational note: to avoid overflow issues, you can multiply a few of the numbers, take the result mod p, and multiply a few more without changing the answer. Eg. (5*9*15) mod 12 = (((5*9) mod 12) * 15) mod 12.]


2) What happens if p is not prime in (1)? Are there any exceptions to this rule? Can you devise a primality testing algorithm from these results? How good is this algorithm speed-wise?


3) Two numbers a and b are called relatively prime if their prime factorizations share no common prime factors. Eg. 10 and 6 are 2*5 and 2*3 which share the factor 2, so they are not relatively prime. The Euclidean algorithm offers a very fast method for determining if two numbers are relatively prime. In pseudocode (partly stolen from Wikipedia),

function IsRelativelyPrime(a, b)
    if gcd(a, b) = 1
        return True
    else
        return False

function gcd(a, b)
    if b = 0
       return a
    else
       return gcd(b, a mod b)

Reconsider (1): the numbers 1, ..., p-1 are each relatively prime to p since p is prime. By contrast, if p is not prime, some of the numbers 1, ..., p-1 are not relatively prime to p. Redo (2) but this time only multiply those numbers 1, ..., p-1 which are relatively prime to p. How does the result depend on p? What happens if p is the power of a prime, like 2^3 = 8? Can you find some simple rules to determine the result in advance without actually multiplying everything out?


[I'd be happy to provide results, proofs, or proof outlines. I'd certainly be interested in original proofs, though without some knowledge of number and/or group theory that's asking a lot.]

[BlindSniper]

I'm certainly no mathematician(60% on this term's test)
But I like to program, and even more than that I like optimizing things.
For the standard prime testing algorithm any prime p you will have Floor(sqrt(p))-1 MOD operations to test if it is a prime. From your statement and A little playing around I made a equation
(p-1)! MOD p = p-1
So far it is true for all primes and 1,although I have not really done any extensive testing to see if there are exceptions, but if it is true then you have got yourself one quick primarily testing algorithm because I have heard that multiplication is 4 times faster than division. I have a suspicion that any value that will result in TRUE will be prime, but it might not be true for all primes.

[Lenggries]

(p-1)! MOD p = p-1

So far it is true for all primes and 1,although I have not really done any extensive testing to see if there are exceptions,

Yes, that is Wilson's Theorem, so it will always be true, although it is most commonly stated as (p-1)! = -1 MOD p, since -1 and (p-1) are the same thing MOD p.

but if it is true then you have got yourself one quick primarily testing algorithm because I have heard that multiplication is 4 times faster than division.

There are a couple problems with this statement. First, because computers would overflow if they did not use modulation as jemediah suggested in his computational note in question 1, a computer would need to repeatedly use modulo during this algorithm, which is basically division anyway, so you completely lose the "4 times faster than division."

Second, the question of how fast a primality test is is mostly relevant in connection with other primality tests. I assume your division method is just a naive sieve, but that is a horrendously slow primality test. In fact, so is Wilson's Theorem, since it's run time is O(p), which means it could only be used on very small numbers (aka nothing like the 200 digit numbers that are actually useful). As far as I'm aware, the fastest deterministic test out there runs at Õ((log p)^6), which basically implies that it grows with the number of digits in p rather than the magnitude of p itself. To make a long story short, there is no such thing as a quick primality test.

[BlindSniper]

Indeed, It's the overflow that kills this one, I was just playing around with small numbers but when I started using bigger numbers I got an overflow. I modified it so it can do 3 digit numbers still faster than my normal method(and then it starts overflowing), but the overflow problem's are not worth it. It seems RSA is still safe.

[jemidiah]

...that is a horrendously slow primality test. In fact, so is Wilson's Theorem, since it's run time is O(p)

I just wanted to emphasize that the naive trial division method is O(sqrt(p)), so the Wilson's theorem test, being O(p), is far worse than even that method for p remotely large.

As far as I'm aware, the fastest deterministic test out there runs at Õ((log p)^6)

Yup, a variant of AKS is down to an exponent of 6, which is likely optimal for that type of algorithm. (According to Lenstra and Pomerance, at least: "A fundamentally new idea would be required to obtain a deterministic primality testing algorithm with run time exponent smaller than 6.")

Indeed, It's the overflow that kills this one, I was just playing around with small numbers but when I started using bigger numbers I got an overflow.

Hmm, you shouldn't get overflow problems until p is around the square root of MaxInt.

It seems RSA is still safe.

Actually, RSA can't be broken by a fast prime test. A fast factoring algorithm would break it, though.

[Lenggries]

I just wanted to emphasize that the naive trial division method is O(sqrt(p)), so the Wilson's theorem test, being O(p), is far worse than even that method for p remotely large.

Yeah, I fiddled with it some. You can definitely reduce Wilson's Therorem to p/2 by pairing n with (p-n) = -n^2 mod p, not that that changes the Big-Oh formula. I wouldn't be surprised if there are other tricks that could reduce it further, though. After all, the naive sieve is only reduced to O(sqrt(p)) due to the non-obvious realization that you only need to consider divisors up to the square root of p. In fact, using the prime number theorem, the naive method can be reduced even further if one has a list of all primes less than the sqrt(p) to O(sqrt(p)/ln(p)).

"A fundamentally new idea would be required to obtain a deterministic primality testing algorithm with run time exponent smaller than 6."

Oooohhh... now I know what to work on if I want to drive myself insane

Hmm, you shouldn't get overflow problems until p is around the square root of MaxInt.

I'm not sure he was taking products in modulo, which means he'll hit an overflow a lot faster than sqrt(MAXINT). Even using an unsigned 64 bit integer, he'd overflow before he could test p=23, since 22! > 2^64. Taking products in modulo, however, I think you are correct with your sqrt(MAXINT) approximation.

Actually, RSA can't be broken by a fast prime test. A fast factoring algorithm would break it, though.

Something else I can drive myself insane with...

[jemidiah]

Even using an unsigned 64 bit integer, he'd overflow before he could test p=23, since 22! > 2^64.

Yes, this combined with "I modified it so it can do 3 digit numbers still faster than my normal method(and then it starts overflowing)" is what confused me. It now occurrs to me that BlindSniper must have been using floating point numbers--for instance, log10(171!) > 309, and MaxDouble (IEEE 754) is around 1.7 x 10^308. In general one should only use integer variables for this type of work. Floating point numbers can and will screw up the results by cutting off bits at the end.


@Lenggries: if you wanted a tractable problem to occupy yourself with, proving the following generalization of Wilson's theorem might be fun: in a finite abelian group G, let #2(G) denote the number of order-2 elements in G.

• If #2(G) = 1, then the product of all elements in G is the unique order 2 element.
• If #2(G) != 1, then the product of all elements is the identity.

Of course, the difficult bit is the #2(G) > 1 case. From this one can immediately pare down the possible answers to the last questions I asked in (3) to +/- 1. Providing a more precise statement requires computing the multiplicative groups of integers mod n, which is remarkably involved--however computational evidence probably guided whoever unraveled that structure originally (Gauss maybe?). I always find it remarkable that (Z/pZ)^x [indeed, (Z/p^a Z)^x] is cyclic for [correction: odd] prime p.