Sage Code 5
sage: 123456^123456 % 50
6
sage: [3]*10
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
sage: timeit('mod(prod([123456]*123456), 50)')
5 loops, best of 3: 60.6 ms per loop # most stupid way
sage: timeit('prod([mod(123456,50)] * 123456)')
125 loops, best of 3: 7.22 ms per loop # naive exponentiation, but stay in Z_50
sage: timeit('mod(123456^123456, 50)')
125 loops, best of 3: 7.92 ms per loop # better exponentiation, but creates a huge number before applying mod
sage: timeit('mod(123456,50)^123456')
625 loops, best of 3: 6.53 µs per loop # both techniques work well together
sage: timeit('power_mod(123456,123456,50)')
625 loops, best of 3: 75 µs per loop # another implementation of the combined techniques; inferior to the previous one.
sage: [n for n in range(100,200) if is_prime(2^n-1)]
[107,127]
sage: p = 2^107-1 # a Mersenne prime
sage: factor(p-1)
2 * 3 * 107 * 6361 * 69431 * 20394401 * 28059810762433
sage: GF(p)
Finite Field of size 162259276829213363391578010288127
sage: g = _.multiplicative_generator()  # _ means the last object, in this case the finite field
sage: g
3
sage: a = randint(2,p-2)
sage: b = randint(2,p-2)
sage: ga = g^a
sage: gb = g^b
sage: timeit('g^a,g^b')
625 loops, best of 3: 13.9 µs per loop
sage: a,b
(17671193841930161262210686036145L, 154730795174908333488383532451076L)
sage: ga^b == gb^a
True # yay, Diffie-Hellman works!
sage: ga^b
4562887700836453333158595763088
sage: [n for n in range(1000,1600) if is_prime(2^n-1)]
[1279]
sage: mod(2,P) ^ ((P-1)/2)
1 # so 2 is indeed a QR mod p
sage: timeit('P = 2^1279-1;mod(2,P) ^ ((P-1)/2)')
125 loops, best of 3: 2.43 ms per loop # even with 1000-bit numbers, this only takes a fraction of a second
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License