View Single Post
Old 2020-02-13, 23:18   #5
carpetpool's Avatar
Nov 2016

26×5 Posts

n is a primitive root mod r, and Agrawal's conjecture holds for (n, r), then n is either prime, or a Carmichael number of order (r-1)/2.

There exist a lower bound such that the smallest Carmichael number of order(m) > Lm.

If these two arguments are true, then there should exist a modified version of the conjecture that is true as we will have necessary and sufficient conditions for which n must be prime.

Assuming the truth of these two arguments, and more specifically, the assumption that the lower bound L (as defined above), exists:


Find a prime r which n is a primitive root (mod r). Then check that

(x - 1)^n = x^n - 1 mod (n, x^r - 1), n < Lm, and (r - 1) > 2*m.

If so, then n is (or should be) prime.

The problem with this test (apart from the unproven assumptions) is that r may be significantly large (for instance, if L = log^2(n) by the GRH). This would make this test (if true) impractical for large numbers. In particular, the complexity is dependent on the size of r.

As pointed out earlier, for any individual prime q, n will be a prime or Carmichael number of order (q-1)/2 if n is a primitive root mod q (condition [1]).

Now for q2, check that the conditions outlined in [1] are true. If so, n must also be (prime) or Carmichael number of order (q2-1)/2. Assume n is not prime. This implies that n is a Carmichael number of order

lcm((q-1)/2, (q2-1)/2) which is equivalent to λ(r)/4 where λ(r) is the Carmichael function of r.

We can r by the conditions outlined in [3] as long as λ(r) > 4*m. However, this would be more practical as we will only have two to run [3] with two smaller primes q and q2 versus r, and this could decrease the complexity (and running time) drastically.

What about r's with more factors? It is feasible to find a set of small primes [q, q2, q3,... qi] for which n is a primitive root mod every prime in the set. Then r is their product and as long as λ(r) > 2^i*m, tests in [3] can be applied to n.

m is defined in [2] to be the smallest integer such that there is no Carmichael number of order m ≤ n.

While I had a hard time attempting to put this all together it appears to be worthwhile to investigate the truth of [1] and [2] if not [3], at the very least. If you have any remarks, or (want) clarification, please let me know.

Last fiddled with by carpetpool on 2020-02-13 at 23:19
carpetpool is offline   Reply With Quote