You will write three small tools: the order of a number, a primitive-root finder and Wilson's test for primes.
The idea. The order of modulo is the least with . A primitive root modulo a prime is a number of order . Wilson's test says is prime exactly when .
Your tasks.
order(a, n). Multiply by step by step until the remainder is , and count the steps.smallest_primitive_root(p). Return the least from upwards with order(g, p) == p - 1.wilson_prime(n). Build modulo in a loop, reducing as you go, and test it against .Run your code once to unlock the worked solution.
Have you tried it?
Do the tasks in the editor first, and run the checker after each one. Its hints help when a check fails. When you are ready, compare your code with this solution.
Log in to join the discussion.
Loading…