SHOW:
|
|
- or go back to the newest paste.
| 1 | def rootmod(k, b, m, verbose=True): | |
| 2 | # Solve x^k==b mod m | |
| 3 | p = phi(m) | |
| 4 | if verbose: print("phi =", p)
| |
| 5 | u = invert(k, p) | |
| 6 | if not u: | |
| 7 | if verbose: print("(k, phi) != 1")
| |
| 8 | return | |
| 9 | else: | |
| 10 | if verbose: print("u =", u)
| |
| 11 | out = pow(b, u, m) | |
| 12 | ||
| 13 | if gcd(b, m) > 1: | |
| 14 | if verbose: print("b^(ku-1) == {} mod {}".format(pow(b, k*u-1, m), m))
| |
| 15 | if out == 0: | |
| 16 | if verbose: print("(b,m) > 1, and the algorithm produced 0.")
| |
| 17 | return 0 | |
| 18 | elif b % m == pow(out, k, m): | |
| 19 | if verbose: print("Despite (b,m) > 1, the algorithm produced {}, which is correct.".format(out))
| |
| 20 | return out + m | |
| 21 | else: | |
| 22 | if verbose: print("(b,m) > 1 and the algorithm produced an incorrect answer {}".format(out))
| |
| 23 | return -1 | |
| 24 | else: # Guaranteed to be correct | |
| 25 | return out | |
| 26 | # Proof: Assume b^u is a solution. Then b^(ku) == b mod m. | |
| 27 | # Thus b^(ku-1) == 1 mod m --> phi(m) | ku-1 by Euler's Thm (and (b,m)=1). | |
| 28 | # But this is ku == 1 mod phi(m) by definition. So b^u is a solution | |
| 29 | # if u is k-inverse mod phi(m). (This also implies (k, phi(m)) = 1.) | |
| 30 | # Note: As some of the above if statements might suggest, the algorithm still sometimes works even if (b,m) > 1. | |
| 31 | ||
| 32 | def huh(count=100, hi=100, verbose=False): | |
| 33 | # Perform a rootmod on "count" number of random triplets k,b,m | |
| 34 | from random import randint | |
| 35 | zero, correct, wrong = 0, 0, 0 | |
| 36 | tot = count | |
| 37 | while count: | |
| 38 | if verbose: print() | |
| 39 | k, b, m = randint(1,hi), randint(1,hi), randint(1,hi) | |
| 40 | x = rootmod(k, b, m, verbose) | |
| 41 | if x is not None: # Ignore (k, phi) > 1 | |
| 42 | count -= 1 | |
| 43 | if x > m: # (b,m) > 1, but it worked anyways | |
| 44 | correct += 1 | |
| 45 | elif x == -1: | |
| 46 | wrong += 1 | |
| 47 | elif x == 0: | |
| 48 | zero += 1 | |
| 49 | print("There were {} zero-results, {} wrong results, {} correct results, and {} with (b, m) = 1".format(zero, wrong, correct, tot-zero-wrong-correct)) |
