mersenneforum.org > Math Quantum trial factoring?
 Register FAQ Search Today's Posts Mark Forums Read

 2020-01-28, 20:43 #1 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 29×79 Posts Quantum trial factoring? Probably a very dumb question, but can Grover's algorithm be used for trial factoring?
 2020-01-29, 00:19 #2 CRGreathouse     Aug 2006 16EA16 Posts I don't see why not. By Holevo's theorem you'd need at least n qubits to factor an n-bit number, and a factor p could be found in time $O(\sqrt{p})=O(\sqrt[4]{N}).$ (Just search for factors of length 20 bits, 40 bits, 80 bits, ..., n/4 bits, n/2 bits.) It's not as fast as QS or NFS though. Last fiddled with by CRGreathouse on 2020-01-29 at 00:33

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 GPU Computing 9 2018-08-31 07:58 jocelynl Math 8 2006-02-01 14:12 JFB Software 23 2004-08-22 05:37 michael Software 23 2004-01-06 08:54 gbvalor Math 4 2003-05-22 02:04

All times are UTC. The time now is 01:23.

Tue Aug 11 01:23:21 UTC 2020 up 24 days, 21:10, 1 user, load averages: 1.46, 1.50, 1.50