What is the fastest integer factorization to break RSA?Largest integer factored by Shor's algorithm?Are there asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm?RSA security assumptions - does breaking the DLP also break RSA?Is there an algorithm for factoring N, which is just as simple as this one, but faster?Integer factorization via geometric mean problemHow can I create an RSA modulus for which no one knows the factors?Effect of $L_n[1/4,c]$ integer factorization on RSA-2048Understanding the Hidden Subgroup Problem specific to Integer FactorizationMore Knowledge Integer FactorizationWhat are some of the best prime factorization algorithms and their effecitvityFermat's factorization method on weak RSA modulus
Is it possible to run Internet Explorer on OS X El Capitan?
How to prevent "they're falling in love" trope
Has there ever been an airliner design involving reducing generator load by installing solar panels?
Is there a hemisphere-neutral way of specifying a season?
I would say: "You are another teacher", but she is a woman and I am a man
A reference to a well-known characterization of scattered compact spaces
Facing a paradox: Earnshaw's theorem in one dimension
How to draw the figure with four pentagons?
How is it possible to have an ability score that is less than 3?
Why doesn't H₄O²⁺ exist?
How do I write bicross product symbols in latex?
I Accidentally Deleted a Stock Terminal Theme
How do conventional missiles fly?
What does it mean to describe someone as a butt steak?
Emailing HOD to enhance faculty application
CEO ridiculed me with gay jokes and grabbed me and wouldn't let go - now getting pushed out of company
Watching something be written to a file live with tail
Why is consensus so controversial in Britain?
Arrow those variables!
Theorems that impeded progress
What do you call someone who asks many questions?
How to take photos in burst mode, without vibration?
Memorizing the Keyboard
AES: Why is it a good practice to use only the first 16bytes of a hash for encryption?
What is the fastest integer factorization to break RSA?
Largest integer factored by Shor's algorithm?Are there asymmetric cryptographic algorithms that are not based on integer factorization and discrete logarithm?RSA security assumptions - does breaking the DLP also break RSA?Is there an algorithm for factoring N, which is just as simple as this one, but faster?Integer factorization via geometric mean problemHow can I create an RSA modulus for which no one knows the factors?Effect of $L_n[1/4,c]$ integer factorization on RSA-2048Understanding the Hidden Subgroup Problem specific to Integer FactorizationMore Knowledge Integer FactorizationWhat are some of the best prime factorization algorithms and their effecitvityFermat's factorization method on weak RSA modulus
$begingroup$
I read on Wikipedia, the fastest Algorithm for breaking RSA is GNFS.
And in one IEEE paper (MVFactor: A method to decrease processing time for factorization algorithm), I read the fastest algorithms are TDM, FFM and VFactor.
Which of these is actually right?
factoring
edited 2 days ago
kelalaka
8,67022351
asked 2 days ago
user56036user56036
412
New contributor
user56036 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
add a comment |
$begingroup$
I read on Wikipedia, the fastest Algorithm for breaking RSA is GNFS.
And in one IEEE paper (MVFactor: A method to decrease processing time for factorization algorithm), I read the fastest algorithms are TDM, FFM and VFactor.
Which of these is actually right?
factoring
edited 2 days ago
kelalaka
8,67022351
asked 2 days ago
user56036user56036
412
New contributor
user56036 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
1
$begingroup$
This conference looks like a paper mill… IEEE is a big organization; its name alone means very little, and it is well-known that many of its publications are essentially academic scams. Except for a single (unused!) citation about the NFS, the authors of this paper appear to be completely unaware of any developments in integer factorization in the past thirty years. Throw it away; ignore the conference; nothing is to be learned here except a lesson about perverse incentives in publish-or-perish academic culture and profiteering academic publishers.
$endgroup$
– Squeamish Ossifrage
yesterday
add a comment |
$begingroup$
I read on Wikipedia, the fastest Algorithm for breaking RSA is GNFS.
And in one IEEE paper (MVFactor: A method to decrease processing time for factorization algorithm), I read the fastest algorithms are TDM, FFM and VFactor.
Which of these is actually right?
factoring
edited 2 days ago
kelalaka
8,67022351
asked 2 days ago
user56036user56036
412
New contributor
user56036 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
$endgroup$
I read on Wikipedia, the fastest Algorithm for breaking RSA is GNFS.
And in one IEEE paper (MVFactor: A method to decrease processing time for factorization algorithm), I read the fastest algorithms are TDM, FFM and VFactor.
Which of these is actually right?
factoring
factoring
edited 2 days ago
kelalaka
8,67022351
asked 2 days ago
user56036user56036
412
New contributor
user56036 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
kelalaka
8,67022351
asked 2 days ago
user56036user56036
412
New contributor
user56036 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 days ago
kelalaka
8,67022351
edited 2 days ago
kelalaka
8,67022351
edited 2 days ago
kelalaka
8,67022351
8,67022351
asked 2 days ago
user56036user56036
412
New contributor
user56036 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
user56036user56036
412
asked 2 days ago
user56036user56036
412
412
New contributor
user56036 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
user56036 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
user56036 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
1
$begingroup$
This conference looks like a paper mill… IEEE is a big organization; its name alone means very little, and it is well-known that many of its publications are essentially academic scams. Except for a single (unused!) citation about the NFS, the authors of this paper appear to be completely unaware of any developments in integer factorization in the past thirty years. Throw it away; ignore the conference; nothing is to be learned here except a lesson about perverse incentives in publish-or-perish academic culture and profiteering academic publishers.
$endgroup$
– Squeamish Ossifrage
yesterday
add a comment |
1
$begingroup$
This conference looks like a paper mill… IEEE is a big organization; its name alone means very little, and it is well-known that many of its publications are essentially academic scams. Except for a single (unused!) citation about the NFS, the authors of this paper appear to be completely unaware of any developments in integer factorization in the past thirty years. Throw it away; ignore the conference; nothing is to be learned here except a lesson about perverse incentives in publish-or-perish academic culture and profiteering academic publishers.
$endgroup$
– Squeamish Ossifrage
yesterday
1
1
$begingroup$
This conference looks like a paper mill… IEEE is a big organization; its name alone means very little, and it is well-known that many of its publications are essentially academic scams. Except for a single (unused!) citation about the NFS, the authors of this paper appear to be completely unaware of any developments in integer factorization in the past thirty years. Throw it away; ignore the conference; nothing is to be learned here except a lesson about perverse incentives in publish-or-perish academic culture and profiteering academic publishers.
$endgroup$
– Squeamish Ossifrage
yesterday
$begingroup$
This conference looks like a paper mill… IEEE is a big organization; its name alone means very little, and it is well-known that many of its publications are essentially academic scams. Except for a single (unused!) citation about the NFS, the authors of this paper appear to be completely unaware of any developments in integer factorization in the past thirty years. Throw it away; ignore the conference; nothing is to be learned here except a lesson about perverse incentives in publish-or-perish academic culture and profiteering academic publishers.
$endgroup$
– Squeamish Ossifrage
yesterday
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
The IEEE paper is silly.
The factorization method they give is quite slow, except for rare cases. For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast...
answered 2 days ago
ponchoponcho
93.7k2146244
$endgroup$
3
$begingroup$
Well I think the point of the paper is to improve upon Fermat-Factoring class algorithms, so it is expected that the given algorithm(s) get beaten by the more standard ones for small sizes, but excel on large inputs with (relatively small) prime differences?
$endgroup$
– SEJPM♦
2 days ago
3
$begingroup$
@SEJPM: if that's the case, then they probably shouldn't go on so much about RSA (where the probability of having a sufficiently small difference is tiny)
$endgroup$
– poncho
2 days ago
add a comment |
$begingroup$
Which of these is actually right?
Both. From reading the abstract it appears the papper doesn't claim that "VFactor" or Fermat Factorization ("FFM") or Trial Division ("TDM") are the best methods in general. However, if the difference between primes $p,q$ with $n=pq$ is really small, like $ll2^100$$;dagger$, then FFM (and probably the VFactor variants as well) will be a lot faster.
Though in general the difference between two same-length random primes is about $sqrtn/2$ which is about $2^1024$ for realistically sized moduli, so these attacks don't work there. Even with 400-bit moduli, which are somewhat easily crackable using a home desktop using the GNFS, this difference is still about $2^200$ and thus way too large.
Of course the implementation of the key generation may be faulty and emit primes in a too small interval and it's in these cases where these specialized algorithms really shine.
$dagger$: "$ll$" meaning "a lot less" here
answered 2 days ago
SEJPM♦SEJPM
29.3k659139
$endgroup$
add a comment |
$begingroup$
Quantum algorithms
There is of course Shor's algorithm, but as this algorithm only runs on quantum computers with a lot of qubits it's not capable to factor larger numbers than $21$ (reference).
There are multiple apparent new records using adiabatic quantum computation, although some are apparently stunts: See fgrieu's answer on a related question.
Classical algorithms
The general number field sieve is the fastest known classical algorithm for factoring numbers over $10^100$.
The Quadratic sieve algorithm is the fastest known classical algorithm for factoring numbers under $10^100$.
answered 2 days ago
AleksanderRasAleksanderRas
2,9471935
$endgroup$
4
$begingroup$
Actually, the factorization of 56153 was a stunt; the factors were deliberately chosen to have a special relation (differed in only 2 bits) and it's easy to factor when the factors have a known relation. AFAIK, the largest number that has been factored to date using a generic quantum factorization algorithm is 21.
$endgroup$
– poncho
2 days ago
$begingroup$
I've always wondered why QS is (at least, consensually said to be) faster than GNFS below a certain thresold (not so consensual), and how much of that is due to lack of work on optimizing GNFS for smaller values.
$endgroup$
– fgrieu
2 days ago
$begingroup$
@poncho As far as I know, all quantum factorization claims to date are stunts, including the 15 and 21 claims. They do a trivial calculation on a tiny quantum computer and then find a tortured way to argue that it factored a prime since that sounds better in the press release. That was the point of the 56153-factorization paper (Quantum factorization of 56153 with only 4 qubits by Dattani and Bryans).
$endgroup$
– benrg
2 days ago
1
$begingroup$
@poncho The paper with the 21-factoring claim is Experimental realisation of Shor's quantum factoring algorithm using qubit recycling by Martin-Lopez et al. I just skimmed it, and as far as I can tell, their actual experiment used a single qubit and a single qutrit. Can a machine with $1 + log_2 3$ qubits run Shor's algorithm on the input 21? They say yes in the title, but I would say no. Dattani and Bryans agree that the factorizations of 15 and 21 "were not genuine implementations of Shor’s algorithm".
$endgroup$
– benrg
2 days ago
$begingroup$
Er, factored a composite.
$endgroup$
– benrg
2 days ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "281"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
user56036 is a new contributor. Be nice, and check out our Code of Conduct.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68480%2fwhat-is-the-fastest-integer-factorization-to-break-rsa%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The IEEE paper is silly.
The factorization method they give is quite slow, except for rare cases. For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast...
answered 2 days ago
ponchoponcho
93.7k2146244
$endgroup$
3
$begingroup$
Well I think the point of the paper is to improve upon Fermat-Factoring class algorithms, so it is expected that the given algorithm(s) get beaten by the more standard ones for small sizes, but excel on large inputs with (relatively small) prime differences?
$endgroup$
– SEJPM♦
2 days ago
3
$begingroup$
@SEJPM: if that's the case, then they probably shouldn't go on so much about RSA (where the probability of having a sufficiently small difference is tiny)
$endgroup$
– poncho
2 days ago
add a comment |
$begingroup$
The IEEE paper is silly.
The factorization method they give is quite slow, except for rare cases. For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast...
answered 2 days ago
ponchoponcho
93.7k2146244
$endgroup$
3
$begingroup$
Well I think the point of the paper is to improve upon Fermat-Factoring class algorithms, so it is expected that the given algorithm(s) get beaten by the more standard ones for small sizes, but excel on large inputs with (relatively small) prime differences?
$endgroup$
– SEJPM♦
2 days ago
3
$begingroup$
@SEJPM: if that's the case, then they probably shouldn't go on so much about RSA (where the probability of having a sufficiently small difference is tiny)
$endgroup$
– poncho
2 days ago
add a comment |
$begingroup$
The IEEE paper is silly.
The factorization method they give is quite slow, except for rare cases. For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast...
answered 2 days ago
ponchoponcho
93.7k2146244
$endgroup$
The IEEE paper is silly.
The factorization method they give is quite slow, except for rare cases. For example, in their table 1, where they proudly show that their improved algorithm takes 653.14 seconds to factor a 67 bit number; well, I just tried it using a more conventional algorithm, and it took 6msec; yes, that's 100,000 times as fast...
answered 2 days ago
ponchoponcho
93.7k2146244
answered 2 days ago
ponchoponcho
93.7k2146244
answered 2 days ago
ponchoponcho
93.7k2146244
answered 2 days ago
ponchoponcho
93.7k2146244
93.7k2146244
3
$begingroup$
Well I think the point of the paper is to improve upon Fermat-Factoring class algorithms, so it is expected that the given algorithm(s) get beaten by the more standard ones for small sizes, but excel on large inputs with (relatively small) prime differences?
$endgroup$
– SEJPM♦
2 days ago
3
$begingroup$
@SEJPM: if that's the case, then they probably shouldn't go on so much about RSA (where the probability of having a sufficiently small difference is tiny)
$endgroup$
– poncho
2 days ago
add a comment |
3
$begingroup$
Well I think the point of the paper is to improve upon Fermat-Factoring class algorithms, so it is expected that the given algorithm(s) get beaten by the more standard ones for small sizes, but excel on large inputs with (relatively small) prime differences?
$endgroup$
– SEJPM♦
2 days ago
3
$begingroup$
@SEJPM: if that's the case, then they probably shouldn't go on so much about RSA (where the probability of having a sufficiently small difference is tiny)
$endgroup$
– poncho
2 days ago
3
3
$begingroup$
Well I think the point of the paper is to improve upon Fermat-Factoring class algorithms, so it is expected that the given algorithm(s) get beaten by the more standard ones for small sizes, but excel on large inputs with (relatively small) prime differences?
$endgroup$
– SEJPM♦
2 days ago
$begingroup$
Well I think the point of the paper is to improve upon Fermat-Factoring class algorithms, so it is expected that the given algorithm(s) get beaten by the more standard ones for small sizes, but excel on large inputs with (relatively small) prime differences?
$endgroup$
– SEJPM♦
2 days ago
3
3
$begingroup$
@SEJPM: if that's the case, then they probably shouldn't go on so much about RSA (where the probability of having a sufficiently small difference is tiny)
$endgroup$
– poncho
2 days ago
$begingroup$
@SEJPM: if that's the case, then they probably shouldn't go on so much about RSA (where the probability of having a sufficiently small difference is tiny)
$endgroup$
– poncho
2 days ago
add a comment |
$begingroup$
Which of these is actually right?
Both. From reading the abstract it appears the papper doesn't claim that "VFactor" or Fermat Factorization ("FFM") or Trial Division ("TDM") are the best methods in general. However, if the difference between primes $p,q$ with $n=pq$ is really small, like $ll2^100$$;dagger$, then FFM (and probably the VFactor variants as well) will be a lot faster.
Though in general the difference between two same-length random primes is about $sqrtn/2$ which is about $2^1024$ for realistically sized moduli, so these attacks don't work there. Even with 400-bit moduli, which are somewhat easily crackable using a home desktop using the GNFS, this difference is still about $2^200$ and thus way too large.
Of course the implementation of the key generation may be faulty and emit primes in a too small interval and it's in these cases where these specialized algorithms really shine.
$dagger$: "$ll$" meaning "a lot less" here
answered 2 days ago
SEJPM♦SEJPM
29.3k659139
$endgroup$
add a comment |
$begingroup$
Which of these is actually right?
Both. From reading the abstract it appears the papper doesn't claim that "VFactor" or Fermat Factorization ("FFM") or Trial Division ("TDM") are the best methods in general. However, if the difference between primes $p,q$ with $n=pq$ is really small, like $ll2^100$$;dagger$, then FFM (and probably the VFactor variants as well) will be a lot faster.
Though in general the difference between two same-length random primes is about $sqrtn/2$ which is about $2^1024$ for realistically sized moduli, so these attacks don't work there. Even with 400-bit moduli, which are somewhat easily crackable using a home desktop using the GNFS, this difference is still about $2^200$ and thus way too large.
Of course the implementation of the key generation may be faulty and emit primes in a too small interval and it's in these cases where these specialized algorithms really shine.
$dagger$: "$ll$" meaning "a lot less" here
answered 2 days ago
SEJPM♦SEJPM
29.3k659139
$endgroup$
add a comment |
$begingroup$
Which of these is actually right?
Both. From reading the abstract it appears the papper doesn't claim that "VFactor" or Fermat Factorization ("FFM") or Trial Division ("TDM") are the best methods in general. However, if the difference between primes $p,q$ with $n=pq$ is really small, like $ll2^100$$;dagger$, then FFM (and probably the VFactor variants as well) will be a lot faster.
Though in general the difference between two same-length random primes is about $sqrtn/2$ which is about $2^1024$ for realistically sized moduli, so these attacks don't work there. Even with 400-bit moduli, which are somewhat easily crackable using a home desktop using the GNFS, this difference is still about $2^200$ and thus way too large.
Of course the implementation of the key generation may be faulty and emit primes in a too small interval and it's in these cases where these specialized algorithms really shine.
$dagger$: "$ll$" meaning "a lot less" here
answered 2 days ago
SEJPM♦SEJPM
29.3k659139
$endgroup$
Which of these is actually right?
Both. From reading the abstract it appears the papper doesn't claim that "VFactor" or Fermat Factorization ("FFM") or Trial Division ("TDM") are the best methods in general. However, if the difference between primes $p,q$ with $n=pq$ is really small, like $ll2^100$$;dagger$, then FFM (and probably the VFactor variants as well) will be a lot faster.
Though in general the difference between two same-length random primes is about $sqrtn/2$ which is about $2^1024$ for realistically sized moduli, so these attacks don't work there. Even with 400-bit moduli, which are somewhat easily crackable using a home desktop using the GNFS, this difference is still about $2^200$ and thus way too large.
Of course the implementation of the key generation may be faulty and emit primes in a too small interval and it's in these cases where these specialized algorithms really shine.
$dagger$: "$ll$" meaning "a lot less" here
answered 2 days ago
SEJPM♦SEJPM
29.3k659139
answered 2 days ago
SEJPM♦SEJPM
29.3k659139
answered 2 days ago
SEJPM♦SEJPM
29.3k659139
answered 2 days ago
SEJPM♦SEJPM
29.3k659139
29.3k659139
add a comment |
add a comment |
$begingroup$
Quantum algorithms
There is of course Shor's algorithm, but as this algorithm only runs on quantum computers with a lot of qubits it's not capable to factor larger numbers than $21$ (reference).
There are multiple apparent new records using adiabatic quantum computation, although some are apparently stunts: See fgrieu's answer on a related question.
Classical algorithms
The general number field sieve is the fastest known classical algorithm for factoring numbers over $10^100$.
The Quadratic sieve algorithm is the fastest known classical algorithm for factoring numbers under $10^100$.
answered 2 days ago
AleksanderRasAleksanderRas
2,9471935
$endgroup$
4
$begingroup$
Actually, the factorization of 56153 was a stunt; the factors were deliberately chosen to have a special relation (differed in only 2 bits) and it's easy to factor when the factors have a known relation. AFAIK, the largest number that has been factored to date using a generic quantum factorization algorithm is 21.
$endgroup$
– poncho
2 days ago
$begingroup$
I've always wondered why QS is (at least, consensually said to be) faster than GNFS below a certain thresold (not so consensual), and how much of that is due to lack of work on optimizing GNFS for smaller values.
$endgroup$
– fgrieu
2 days ago
$begingroup$
@poncho As far as I know, all quantum factorization claims to date are stunts, including the 15 and 21 claims. They do a trivial calculation on a tiny quantum computer and then find a tortured way to argue that it factored a prime since that sounds better in the press release. That was the point of the 56153-factorization paper (Quantum factorization of 56153 with only 4 qubits by Dattani and Bryans).
$endgroup$
– benrg
2 days ago
1
$begingroup$
@poncho The paper with the 21-factoring claim is Experimental realisation of Shor's quantum factoring algorithm using qubit recycling by Martin-Lopez et al. I just skimmed it, and as far as I can tell, their actual experiment used a single qubit and a single qutrit. Can a machine with $1 + log_2 3$ qubits run Shor's algorithm on the input 21? They say yes in the title, but I would say no. Dattani and Bryans agree that the factorizations of 15 and 21 "were not genuine implementations of Shor’s algorithm".
$endgroup$
– benrg
2 days ago
$begingroup$
Er, factored a composite.
$endgroup$
– benrg
2 days ago
add a comment |
$begingroup$
Quantum algorithms
There is of course Shor's algorithm, but as this algorithm only runs on quantum computers with a lot of qubits it's not capable to factor larger numbers than $21$ (reference).
There are multiple apparent new records using adiabatic quantum computation, although some are apparently stunts: See fgrieu's answer on a related question.
Classical algorithms
The general number field sieve is the fastest known classical algorithm for factoring numbers over $10^100$.
The Quadratic sieve algorithm is the fastest known classical algorithm for factoring numbers under $10^100$.
answered 2 days ago
AleksanderRasAleksanderRas
2,9471935
$endgroup$
4
$begingroup$
Actually, the factorization of 56153 was a stunt; the factors were deliberately chosen to have a special relation (differed in only 2 bits) and it's easy to factor when the factors have a known relation. AFAIK, the largest number that has been factored to date using a generic quantum factorization algorithm is 21.
$endgroup$
– poncho
2 days ago
$begingroup$
I've always wondered why QS is (at least, consensually said to be) faster than GNFS below a certain thresold (not so consensual), and how much of that is due to lack of work on optimizing GNFS for smaller values.
$endgroup$
– fgrieu
2 days ago
$begingroup$
@poncho As far as I know, all quantum factorization claims to date are stunts, including the 15 and 21 claims. They do a trivial calculation on a tiny quantum computer and then find a tortured way to argue that it factored a prime since that sounds better in the press release. That was the point of the 56153-factorization paper (Quantum factorization of 56153 with only 4 qubits by Dattani and Bryans).
$endgroup$
– benrg
2 days ago
1
$begingroup$
@poncho The paper with the 21-factoring claim is Experimental realisation of Shor's quantum factoring algorithm using qubit recycling by Martin-Lopez et al. I just skimmed it, and as far as I can tell, their actual experiment used a single qubit and a single qutrit. Can a machine with $1 + log_2 3$ qubits run Shor's algorithm on the input 21? They say yes in the title, but I would say no. Dattani and Bryans agree that the factorizations of 15 and 21 "were not genuine implementations of Shor’s algorithm".
$endgroup$
– benrg
2 days ago
$begingroup$
Er, factored a composite.
$endgroup$
– benrg
2 days ago
add a comment |
$begingroup$
Quantum algorithms
There is of course Shor's algorithm, but as this algorithm only runs on quantum computers with a lot of qubits it's not capable to factor larger numbers than $21$ (reference).
There are multiple apparent new records using adiabatic quantum computation, although some are apparently stunts: See fgrieu's answer on a related question.
Classical algorithms
The general number field sieve is the fastest known classical algorithm for factoring numbers over $10^100$.
The Quadratic sieve algorithm is the fastest known classical algorithm for factoring numbers under $10^100$.
answered 2 days ago
AleksanderRasAleksanderRas
2,9471935
$endgroup$
Quantum algorithms
There is of course Shor's algorithm, but as this algorithm only runs on quantum computers with a lot of qubits it's not capable to factor larger numbers than $21$ (reference).
There are multiple apparent new records using adiabatic quantum computation, although some are apparently stunts: See fgrieu's answer on a related question.
Classical algorithms
The general number field sieve is the fastest known classical algorithm for factoring numbers over $10^100$.
The Quadratic sieve algorithm is the fastest known classical algorithm for factoring numbers under $10^100$.
answered 2 days ago
AleksanderRasAleksanderRas
2,9471935
edited 2 days ago
answered 2 days ago
AleksanderRasAleksanderRas
2,9471935
answered 2 days ago
AleksanderRasAleksanderRas
2,9471935
answered 2 days ago
AleksanderRasAleksanderRas
2,9471935
2,9471935
4
$begingroup$
Actually, the factorization of 56153 was a stunt; the factors were deliberately chosen to have a special relation (differed in only 2 bits) and it's easy to factor when the factors have a known relation. AFAIK, the largest number that has been factored to date using a generic quantum factorization algorithm is 21.
$endgroup$
– poncho
2 days ago
$begingroup$
I've always wondered why QS is (at least, consensually said to be) faster than GNFS below a certain thresold (not so consensual), and how much of that is due to lack of work on optimizing GNFS for smaller values.
$endgroup$
– fgrieu
2 days ago
$begingroup$
@poncho As far as I know, all quantum factorization claims to date are stunts, including the 15 and 21 claims. They do a trivial calculation on a tiny quantum computer and then find a tortured way to argue that it factored a prime since that sounds better in the press release. That was the point of the 56153-factorization paper (Quantum factorization of 56153 with only 4 qubits by Dattani and Bryans).
$endgroup$
– benrg
2 days ago
1
$begingroup$
@poncho The paper with the 21-factoring claim is Experimental realisation of Shor's quantum factoring algorithm using qubit recycling by Martin-Lopez et al. I just skimmed it, and as far as I can tell, their actual experiment used a single qubit and a single qutrit. Can a machine with $1 + log_2 3$ qubits run Shor's algorithm on the input 21? They say yes in the title, but I would say no. Dattani and Bryans agree that the factorizations of 15 and 21 "were not genuine implementations of Shor’s algorithm".
$endgroup$
– benrg
2 days ago
$begingroup$
Er, factored a composite.
$endgroup$
– benrg
2 days ago
add a comment |
4
$begingroup$
Actually, the factorization of 56153 was a stunt; the factors were deliberately chosen to have a special relation (differed in only 2 bits) and it's easy to factor when the factors have a known relation. AFAIK, the largest number that has been factored to date using a generic quantum factorization algorithm is 21.
$endgroup$
– poncho
2 days ago
$begingroup$
I've always wondered why QS is (at least, consensually said to be) faster than GNFS below a certain thresold (not so consensual), and how much of that is due to lack of work on optimizing GNFS for smaller values.
$endgroup$
– fgrieu
2 days ago
$begingroup$
@poncho As far as I know, all quantum factorization claims to date are stunts, including the 15 and 21 claims. They do a trivial calculation on a tiny quantum computer and then find a tortured way to argue that it factored a prime since that sounds better in the press release. That was the point of the 56153-factorization paper (Quantum factorization of 56153 with only 4 qubits by Dattani and Bryans).
$endgroup$
– benrg
2 days ago
1
$begingroup$
@poncho The paper with the 21-factoring claim is Experimental realisation of Shor's quantum factoring algorithm using qubit recycling by Martin-Lopez et al. I just skimmed it, and as far as I can tell, their actual experiment used a single qubit and a single qutrit. Can a machine with $1 + log_2 3$ qubits run Shor's algorithm on the input 21? They say yes in the title, but I would say no. Dattani and Bryans agree that the factorizations of 15 and 21 "were not genuine implementations of Shor’s algorithm".
$endgroup$
– benrg
2 days ago
$begingroup$
Er, factored a composite.
$endgroup$
– benrg
2 days ago
4
4
$begingroup$
Actually, the factorization of 56153 was a stunt; the factors were deliberately chosen to have a special relation (differed in only 2 bits) and it's easy to factor when the factors have a known relation. AFAIK, the largest number that has been factored to date using a generic quantum factorization algorithm is 21.
$endgroup$
– poncho
2 days ago
$begingroup$
Actually, the factorization of 56153 was a stunt; the factors were deliberately chosen to have a special relation (differed in only 2 bits) and it's easy to factor when the factors have a known relation. AFAIK, the largest number that has been factored to date using a generic quantum factorization algorithm is 21.
$endgroup$
– poncho
2 days ago
$begingroup$
I've always wondered why QS is (at least, consensually said to be) faster than GNFS below a certain thresold (not so consensual), and how much of that is due to lack of work on optimizing GNFS for smaller values.
$endgroup$
– fgrieu
2 days ago
$begingroup$
I've always wondered why QS is (at least, consensually said to be) faster than GNFS below a certain thresold (not so consensual), and how much of that is due to lack of work on optimizing GNFS for smaller values.
$endgroup$
– fgrieu
2 days ago
$begingroup$
@poncho As far as I know, all quantum factorization claims to date are stunts, including the 15 and 21 claims. They do a trivial calculation on a tiny quantum computer and then find a tortured way to argue that it factored a prime since that sounds better in the press release. That was the point of the 56153-factorization paper (Quantum factorization of 56153 with only 4 qubits by Dattani and Bryans).
$endgroup$
– benrg
2 days ago
$begingroup$
@poncho As far as I know, all quantum factorization claims to date are stunts, including the 15 and 21 claims. They do a trivial calculation on a tiny quantum computer and then find a tortured way to argue that it factored a prime since that sounds better in the press release. That was the point of the 56153-factorization paper (Quantum factorization of 56153 with only 4 qubits by Dattani and Bryans).
$endgroup$
– benrg
2 days ago
1
1
$begingroup$
@poncho The paper with the 21-factoring claim is Experimental realisation of Shor's quantum factoring algorithm using qubit recycling by Martin-Lopez et al. I just skimmed it, and as far as I can tell, their actual experiment used a single qubit and a single qutrit. Can a machine with $1 + log_2 3$ qubits run Shor's algorithm on the input 21? They say yes in the title, but I would say no. Dattani and Bryans agree that the factorizations of 15 and 21 "were not genuine implementations of Shor’s algorithm".
$endgroup$
– benrg
2 days ago
$begingroup$
@poncho The paper with the 21-factoring claim is Experimental realisation of Shor's quantum factoring algorithm using qubit recycling by Martin-Lopez et al. I just skimmed it, and as far as I can tell, their actual experiment used a single qubit and a single qutrit. Can a machine with $1 + log_2 3$ qubits run Shor's algorithm on the input 21? They say yes in the title, but I would say no. Dattani and Bryans agree that the factorizations of 15 and 21 "were not genuine implementations of Shor’s algorithm".
$endgroup$
– benrg
2 days ago
$begingroup$
Er, factored a composite.
$endgroup$
– benrg
2 days ago
$begingroup$
Er, factored a composite.
$endgroup$
– benrg
2 days ago
add a comment |
user56036 is a new contributor. Be nice, and check out our Code of Conduct.
user56036 is a new contributor. Be nice, and check out our Code of Conduct.
user56036 is a new contributor. Be nice, and check out our Code of Conduct.
user56036 is a new contributor. Be nice, and check out our Code of Conduct.
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f68480%2fwhat-is-the-fastest-integer-factorization-to-break-rsa%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
This conference looks like a paper mill… IEEE is a big organization; its name alone means very little, and it is well-known that many of its publications are essentially academic scams. Except for a single (unused!) citation about the NFS, the authors of this paper appear to be completely unaware of any developments in integer factorization in the past thirty years. Throw it away; ignore the conference; nothing is to be learned here except a lesson about perverse incentives in publish-or-perish academic culture and profiteering academic publishers.
$endgroup$
– Squeamish Ossifrage
yesterday