Fast Powering Mod
2
to the power of
1
(mod 341)
8 ^ 340 = (8 ^ 170) ^ 2
8 ^ 170 = (8 ^ 85) ^ 2
8 ^ 85 = (8 ^ 84) * 8
8 ^ 84 = (8 ^ 42) ^ 2
8 ^ 42 = (8 ^ 21) ^ 2
8 ^ 21 = (8 ^ 20) * 8
8 ^ 20 = (8 ^ 10) ^ 2
8 ^ 10 = (8 ^ 5) ^ 2
8 ^ 5 = (8 ^ 4) * 8
8 ^ 4 = (8 ^ 2) ^ 2
8 ^ 2 = (8) ^ 2
--------------------
8 ^ 2 = (8) ^ 2 --> 8 ^ 2 = 64 -> 64 (mod 341)
8 ^ 4 = (8 ^ 2) ^ 2 --> 64 ^ 2 = 4096 -> 4 (mod 341)
8 ^ 5 = (8 ^ 4) * 8 --> 4 * 8 = 32 -> 32 (mod 341)
8 ^ 10 = (8 ^ 5) ^ 2 --> 32 ^ 2 = 1024 -> 1 (mod 341)
'--> non trivial sqrt
8 ^ 20 = (8 ^ 10) ^ 2 --> 1 ^ 2 = 1 -> 1 (mod 341)
8 ^ 21 = (8 ^ 20) * 8 --> 1 * 8 = 8 -> 8 (mod 341)
8 ^ 42 = (8 ^ 21) ^ 2 --> 8 ^ 2 = 64 -> 64 (mod 341)
8 ^ 84 = (8 ^ 42) ^ 2 --> 64 ^ 2 = 4096 -> 4 (mod 341)
8 ^ 85 = (8 ^ 84) * 8 --> 4 * 8 = 32 -> 32 (mod 341)
8 ^ 170 = (8 ^ 85) ^ 2 --> 32 ^ 2 = 1024 -> 1 (mod 341)
'--> non trivial sqrt
8 ^ 340 = (8 ^ 170) ^ 2 --> 1 ^ 2 = 1 -> 1 (mod 341)
--------------------
8 ^ 340 = 1 (mod 341)
341 is not prime because it has a Non-Trivial-Sqrt
impressum