Quantum trial factoring?

ixfd64 · 2020-01-28, 20:43

Probably a very dumb question, but can Grover's algorithm be used for trial factoring?

CRGreathouse · 2020-01-29, 00:19

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.

2020-01-28, 20:43	#1
ixfd64 Bemusing Prompter "Danny" Dec 2002 California 2·5·239 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 3×1,993 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
Trial Factoring on AMD/ATI GPU's?	Stargate38	GPU Computing	9	2018-08-31 07:58
trial factoring and P-1	jocelynl	Math	8	2006-02-01 14:12
over trial factoring	JFB	Software	23	2004-08-22 05:37
How to only do Trial Factoring?	michael	Software	23	2004-01-06 08:54
About trial factoring	gbvalor	Math	4	2003-05-22 02:04