Talk:Shor's algorithm: Difference between revisions

Revision as of 06:03, 14 May 2006

Revision as of 07:03, 30 May 2006

Line 39:

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 rks 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)

: ''Trivial'' factors (or divisors) of N are by definition N and 1. Nontrivial factors are all factors of N other than N and 1. So the article was correct. [[User:84.227.226.196|84.227.226.196]] 07:03, 30 May 2006 (UTC)

== external link removed ==