Assignment 1 and the Maple programs: most common letters and affine transform
Check your number is composite using the Lucas test. Use Fermat factorisation with 3 times your number. After how many iterations will it work if you just use the number itself? How about 5 times? Does it work with 2 times? How long would it take to use trial division to factorise it? Use Pollard p-1 and Pollard rho (should work in less than 20 steps) Please use calculators and/or Maple to simplify your work in case of arithmetical errors, i am just trying to test that you can do the algorithms, not arithmetic! The extra notes on Pollard factoring are here
Find the gcd and an llc for (576,153) and (733,419)
Show, using induction, that gcd(a, b, ...,z) = gcd(...gcd(gcd(a,b),c)...,z)
What is the gcd of 261 and 69 ? ans:(highlight to see) 3 = 9*261 -34*69
Prime factors of 4807 ? ans: 11*19*23
Primes between 250 and 280 ? ans: 251, 257, 263, 269, 271, 277
a | (b-c) and a | (b+c) implies a | b ? ans: no. a=2, b=5, c=1 true if a is odd though, since b-c = ka and b+c = la imply that 2b = (k+l)a so a|2b and so if a odd then a|b.
What are the solutions to these congruences?
10x = 9 (mod 33),
46x = 14 (mod 62),
41x = -127 (mod 239),
ans:
x = 24 (mod 33),
x = 3 (mod 31),
x = 96 (mod 239)
What is the solution to the three equations above simultaneously?
ans:
x = 155685 (mod 244497),
Evaluate phi, sigma and tau for n=128, 129, 130, 131, 132
ans:
n=128: 64, 255, 8
n=129: 84, 176, 4
n=130: 48, 252, 8
n=131: 130, 132, 2
n=132: 40, 336, 12
You are told that "dodamrgdware" has been encoded using affine encoding
using the alphabet "adegmnorsvw" with encoding C = 7P + 9 (mod 11).
Work out the decoding equation and find out the message:
ans:
P = 8C + 5 = 5-3C (mod 11) so "evenmoresnow"
What is 11^87 (mod 18) ? What are the solutions to 2x^2+x== 24 (mod 63)
ans:
17 (mod 18)
x== 15,16,43,51 (mod 63)