3. Alice is playing a FactorFinding game with herself. The integer factorization is not exciting enough...

Transcribed Image Text:

3. Alice is playing a FactorFinding game with herself. The integer factorization is not exciting enough so she decides to consider another number system. - Alice thinks about the "complex integers", i.e. a +bi where a, b are integers and i² example, • addition: (1 + 2i) + (3 + 4i) = 4 + 6i; multiplication: (1 + 2i)(3+4i) = 3−8+ (6 + 4)i = −5+ 10i ● -1. For She then plays the game as follows. Alice starts with an arbitrary "complex integer” a₁ +b₁i and k 1. Alice tries to find ak+1+bk+1i that divides ak +bki which means there exist two integers c and d such that (ak+1 + bk+1i)(c + di) = ak + bki. If |c| + |d| ≤ 1, then the game terminates. Otherwise, she increments k and repeats this step. Question: Can Alice continue the game forever? If yes, give an example infinite run. If not, prove it by the potential-function method. Hint: Try the potential function Þ(a + bi) = a² + 6². Solution: 3. Alice is playing a FactorFinding game with herself. The integer factorization is not exciting enough so she decides to consider another number system. - Alice thinks about the "complex integers", i.e. a +bi where a, b are integers and i² example, • addition: (1 + 2i) + (3 + 4i) = 4 + 6i; multiplication: (1 + 2i)(3+4i) = 3−8+ (6 + 4)i = −5+ 10i ● -1. For She then plays the game as follows. Alice starts with an arbitrary "complex integer” a₁ +b₁i and k 1. Alice tries to find ak+1+bk+1i that divides ak +bki which means there exist two integers c and d such that (ak+1 + bk+1i)(c + di) = ak + bki. If |c| + |d| ≤ 1, then the game terminates. Otherwise, she increments k and repeats this step. Question: Can Alice continue the game forever? If yes, give an example infinite run. If not, prove it by the potential-function method. Hint: Try the potential function Þ(a + bi) = a² + 6². Solution:

Answer rating: 100% (QA)

Yes Alice can continue the game forever Heres an example infinite run 1 Alice starts with a1 b1i 1 1... View the full answer