Number Theory 2

Question 1

What are secure channels examples used in daily life?

Answer 1

• IPSAC to establish VPNs
• SSH establishes secure channels

Question 2

What are secure channels good for?

Answer 2

• Secure pipe between the sender and the receiver
• Gives message confidentiality and integrity ( we can detect tampering)

Question 3

What are the two applications of the Fermat Theorem? what is the formulas?

Answer 3

1- To find inverse
x^-1 = x ^(p-2) (mod p)
2- To generate prime numbers
a^(n-1) == 1 (mod n)

Question 4

What is the formula for Fermet’s Theorem?

Answer 4

x^(p-1) = 1 (mod p)

Question 5

How can Fermat’s Theorem be used to generate prime numbers?

Answer 5

Choose a random prime number n and keep testing Z_n to see if it is actually a prime by choosing a random a and if it fulfills fermats theorem everytime then it is prime, if it fails its not prime.

Question 6

What are Fermat liars and what are carmicheal numbers?

Answer 6

• There are integers a, that are Fermat liars, that is, a^(n-1 ) ≡ 1 (mod n) even if n is composite. In this case, n is called a Fermat pseudoprime to base a.
  
  • A Fermat liar is a number a that incorrectly “testifies” that n is prime.
• There are composite Carmichael numbers n, for which a^(n-1)≡ 1 (mod n) holds for all a coprime with n.
  
  • There are certain numbers that pass this test, rare but infinitely many

Question 7

What is Euler’s Totient theorem?

Answer 7

Here, φ(n) is Euler’s totient function, which counts the number of positive integers less than or equal to n that are coprime to n. In other words, it measures the number of integers within the range from 1 to n that share no common factors with n.

Question 8

Why does it matter to know the group order φ(n) in Euler’s theorem?

Answer 8

Allows you to
- Cancel out elements x by raising it to φ(n) and resolve computations that are otherwise hard
- Gives you a computational advantage against an adversary

Question 9

When is eulers theorem intractable?

Answer 9

Intractable, if prime factorisation of N is unknown

Question 10

How hard is computing the eth root when you dont know the group order?

Answer 10

• If we have a prime modulus It’s easy to compute the e^th root as long as e is coprime with p-1 (group order)
  
  • Because we can choose d as multiplicative inverse of e (they will cancel each other out which can allow us to get a shortcut

If I dont have a prime modulus and its composite and i dont know the order its very hard to compute

Question 11

How can you compute the eth root practically if the group order is known?

Answer 11

If we know N, p, q and e

we can compute the eth root, by computing phi(N) = (p -1) x ( q - 1)

then get the modular inverse by doing EEA(e, phi(N) )