mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2020-01-28, 20:43   #1
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

29×79 Posts
Default Quantum trial factoring?

Probably a very dumb question, but can Grover's algorithm be used for trial factoring?
ixfd64 is online now   Reply With Quote
Old 2020-01-29, 00:19   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

16EA16 Posts
Default

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
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.