Timeline for Calculate the period (like in Shor's algorithm) from the factors?
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 22, 2023 at 23:53 | answer | added | Martin Ekerå | timeline score: 2 | |
| Mar 22, 2023 at 13:31 | answer | added | Sam Jaques | timeline score: 2 | |
| Mar 9, 2022 at 17:40 | history | edited | Doriano Brogioli | CC BY-SA 4.0 |
edited body
|
| Mar 8, 2022 at 9:37 | history | edited | Doriano Brogioli | CC BY-SA 4.0 |
added 69 characters in body
|
| Mar 8, 2022 at 9:36 | comment | added | Doriano Brogioli | I edited the question to clarify that I need the minimum. With your method, I get a multiple of the required r, so I still have to make a factorization, while I'm asking for a polynomial time algorithm. Is this correct? The final aim is this: mathoverflow.net/questions/417142/… That problem reduces to this question noticing that we can uniformly sample numbers in the form of their factors. | |
| Mar 7, 2022 at 19:54 | comment | added | Mateus Araújo | If $N=pq$ then $a^{(p-1)(q-1)} = 1 \mod N$, for $a$ belonging to the multiplicative group modulo $N$. Is this what you want? It gives you a period of the function, albeit not necessarily the minimal one. | |
| Mar 7, 2022 at 19:42 | comment | added | Mateus Araújo | It doesn't answer your question, but maybe you'll find it interesting: this hilarious paper shows that if the factors of $N$ are known it is easy to find $a$ such that the period is equal to 2. | |
| Mar 7, 2022 at 9:31 | history | edited | Doriano Brogioli | CC BY-SA 4.0 |
added 9 characters in body
|
| Mar 7, 2022 at 9:11 | history | edited | Doriano Brogioli | CC BY-SA 4.0 |
added 250 characters in body
|
| Mar 6, 2022 at 11:45 | history | edited | Doriano Brogioli |
edited tags
|
|
| Mar 6, 2022 at 11:43 | comment | added | Doriano Brogioli | The comments should be supported by literature references. Can you provide a reference where this question is explicitly answered? I do not think so. The answer must be explicit, it is not enough to cite a generic book on number theory. About the second part of the comment, yes, maybe another forum would be more appropriate, but "quantum computing" is much more responsive than others. Actually, you claim that you know the answer: this means that this forum is not so wrong. | |
| Mar 5, 2022 at 18:14 | comment | added | Ron Cohen | This question is classic, and much more should be asked in another forum | |
| Mar 5, 2022 at 17:37 | history | asked | Doriano Brogioli | CC BY-SA 4.0 |