Talk:Shor's algorithm: Difference between revisions

Revision as of 14:47, 16 February 2006

Revision as of 01:37, 5 March 2006

Line 31:

It should be ''trivial'' factor, shouldn't it? I'll change it myself soon if no-one replies. [[User:Aaron McDaid|Aaron McDaid]] <small>([[User_talk:Aaron McDaid|talk]] - [[Special:Contributions/Aaron McDaid|contribs]]) </small> 10:34, 12 February 2006 (UTC)

: No. The step is correct. The chances that ''gcd(a,N) > 1'' are very small when factoring large integers. So in practice this step should always fail to find a factor. Note, however, that the remainder of the algorithm only worksrks if ''gcd(a,N)=1''. Furthermore testing ''gcd(a,N)'' is important when factoring small integers such as 15. [[User:24.228.93.22|24.228.93.22]] 14:47, 16 February 2006 (UTC)

[[Category:To do]]