I Finding the period in a modular exponentiation sequence

  • I
  • Thread starter Thread starter Bob Walance
  • Start date Start date
  • Tags Tags
    Period Sequence
AI Thread Summary
The discussion centers on understanding the period of a modular exponentiation sequence related to Shor's algorithm. The period is established as 4, with the sequence repeating every fourth value when the first value is congruent to 1. It explains that when the modular exponentiation returns to 1, the period can be calculated as the difference between the current index and the initial index where the value was 1. For classical computers, finding the first occurrence of 1 after the initial value is key, while quantum computers can leverage the quantum Fourier transform for a more efficient solution. This highlights the differences in computational approaches to determining the period in modular exponentiation sequences.
Bob Walance
Insights Author
Gold Member
Messages
82
Reaction score
55
This question is related to Shor's algorithm and its use of modular exponentiation.

In the table below, the period of the sequence in the third column is obviously equal to 4. That is, its value repeats every fourth row.

What I am trying to find out is why it is that when the first value in third column is congruent with 1 then the period of the sequence is the corresponding value of 'r'.

I have searched for an answer but have had no luck. It might be that I don't know how to phrase the question properly to find an answer on Google.

r
2^r
(2^r) % 15
0​
1​
1​
1​
2​
2​
2​
4​
4​
3​
8​
8​
4​
16​
1​
5​
32​
2​
6​
64​
4​
7​
128​
8​
8​
256​
1​
9​
512​
2​
10​
1024​
4​
11​
2048​
8​
12​
4096​
1​
13​
8192​
2​
 
Last edited:
Mathematics news on Phys.org
The answer to this question was provided to me at math.stackexchange. I have added an r=0 entry to the table above to make this answer clearer:

1) When r = 0 (let's call this r0) then '(2^0) % 15' is congruent with 1.
2) As r is incremented beyond 0 then '(2^r) % 15' will change from 1 to some other value.
3) When '(2^r) % 15' is equal to 1 again (at rP) then the period of the modular exponentiation sequence will be rP-r0=rP.

If the search for the period of this modular exponentiation sequence is done with a classical computer then it is convenient to find the first r (after r=0) that has the modexp value congruent with 1 again. However, if the search is done using a quantum computer then the quantum Fourier transform would be more efficient in finding the sequence's period.
 
Suppose ,instead of the usual x,y coordinate system with an I basis vector along the x -axis and a corresponding j basis vector along the y-axis we instead have a different pair of basis vectors ,call them e and f along their respective axes. I have seen that this is an important subject in maths My question is what physical applications does such a model apply to? I am asking here because I have devoted quite a lot of time in the past to understanding convectors and the dual...
Fermat's Last Theorem has long been one of the most famous mathematical problems, and is now one of the most famous theorems. It simply states that the equation $$ a^n+b^n=c^n $$ has no solutions with positive integers if ##n>2.## It was named after Pierre de Fermat (1607-1665). The problem itself stems from the book Arithmetica by Diophantus of Alexandria. It gained popularity because Fermat noted in his copy "Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et...
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. In Dirac’s Principles of Quantum Mechanics published in 1930 he introduced a “convenient notation” he referred to as a “delta function” which he treated as a continuum analog to the discrete Kronecker delta. The Kronecker delta is simply the indexed components of the identity operator in matrix algebra Source: https://www.physicsforums.com/insights/what-exactly-is-diracs-delta-function/ by...

Similar threads

Back
Top