Re: A prime problem that even quantum computing can't solve

In sci.physics.research message <g2bjb7$4u7$2@xxxxxxxxx>, Sat, 7 Jun
2008 19:45:52, Phillip Helbig---remove CLOTHES to reply <helbig@xxxxxxxx
ltiCLOTHESvax.de> posted:

This is, more or less, a tautology. Are you sure that wasn't the 1
April edition of Nature? A prime number, by definition, is a number
which has no factors other than the trivial ones of itself and 1. Thus,
it can never be factored (except trivially).

If a number is prime and is known to be prime then its factoring is
trivial, whatever its size.

If a large number is not known to be prime (as opposed to known not to
be prime), then its factoring is often non-trivial, even if the number
is prime. AIUI, there are ways of proving fairly readily that a number
is almost certainly prime, or that it is certainly not prime; but
anything that correctly factors a number getting only the number and 1
gives an assured proof that the number is prime. That's a non-trivial
task.

In some crypto, AIUI, an encoder wants to obtain large prime numbers; in
the corresponding code-breaking, a breaker wants to factorise the
product of large primes.

--
(c) John Stockton, near London. *@merlyn.demon.co.uk/?.?.Stockton@xxxxxxxxxxx
Web <URL:http://www.merlyn.demon.co.uk/> - FAQish topics, acronyms, & links.
Correct <= 4-line sig. separator as above, a line precisely "-- " (SoRFC1036)
Do not Mail News to me. Before a reply, quote with ">" or "> " (SoRFC1036)

.

Relevant Pages

  • Re:JSH: Bored, bored, bored again
    ... made to work for factoring huge numbers but I'd think that'd take some ... There is an insistent need to die in our behaviour, ... nature always remains true so now the most dominant nation on the ... We the people of the United States of America...were betrayed...but we ...
    (sci.math)
  • JSH: Bored, bored, bored again
    ... made to work for factoring huge numbers but I'd think that'd take some ... nature always remains true so now the most dominant nation on the ... we are capable of nuking you. ... We the people of the United States of America...were betrayed...but we ...
    (sci.math)
  • Re: JSH: Bored, bored, bored again
    ... made to work for factoring huge numbers but I'd think that'd take some ... nature always remains true so now the most dominant nation on the ... we are capable of nuking you. ... We the people of the United States of America...were betrayed...but we ...
    (sci.math)
  • A prime problem that even quantum computing cant solve
    ... In Nature dd 29 May 2008 at page 586 we read: ... One thing that even quantum computing can never ... accomplish is "factoring large prime numbers". ...
    (sci.physics.research)
Loading