[math-fun] Mathematical Trick Helps Smash Record For the Largest Quantum Factorization
http://science-beta.slashdot.org/story/14/12/03/1551239/mathematical-trick-h... <http://beta.slashdot.org/%7ESoulskill>Soulskill posted about an hour ago | from the still-slower-than-a-12-year-old dept. <http://beta.slashdot.org/index2.pl?fhfilter=math> Math <http://beta.slashdot.org/index2.pl?fhfilter=math> <http://science-beta.slashdot.org/story/14/12/03/1551239/mathematical-trick-helps-smash-record-for-the-largest-quantum-factorization>16 <http://beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: One of the big applications for quantum computers is finding the prime factors of large numbers, a technique that can help break most modern cryptographic codes. Back in 2012, a team of Chinese physicists used a nuclear magnetic resonance quantum computer with 4 qubits to factor the number 143 (11 x 13), the largest quantum factorization ever performed. Now a <http://arxiv.org/abs/1411.6758>pair of mathematicians say the technique used by the Chinese team is more powerful than originally thought. Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. So instead of just factoring 143, <https://medium.com/the-physics-arxiv-blog/the-mathematical-trick-that-helped-smash-the-record-for-the-largest-number-ever-factorised-by-a-77fde88499>the Chinese team actually quantum factored the number 56153 (233 x 241, which differ by two bits when written in binary). That's the largest quantum factorization by some margin. The mathematicians point out that their discovery will not help code breakers since they'd need to know in advance that the factors differ by 2 bits, which seems unlikely. What's more, the technique relies on only 4 qubits and so can be easily reproduced on a classical computer. --- co-chair http://ocjug.com/
Something seems odd in the cited article. It says "Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. " Without doing any calculation it seems the Fermat prime 65,537 plus 6 times the prime would be a larger example 4,295,491,591 ----- Original Message ----- From: "Ray Tayek" <rtayek@ca.rr.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, December 03, 2014 9:58 AM Subject: [math-fun] Mathematical Trick Helps Smash Record For the Largest Quantum Factorization
http://science-beta.slashdot.org/story/14/12/03/1551239/mathematical-trick-h...
<http://beta.slashdot.org/%7ESoulskill>Soulskill posted about an hour ago | from the still-slower-than-a-12-year-old dept.
<http://beta.slashdot.org/index2.pl?fhfilter=math> Math
<http://beta.slashdot.org/index2.pl?fhfilter=math> <http://science-beta.slashdot.org/story/14/12/03/1551239/mathematical-trick-helps-smash-record-for-the-largest-quantum-factorization>16
<http://beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: One of the big applications for quantum computers is finding the prime factors of large numbers, a technique that can help break most modern cryptographic codes. Back in 2012, a team of Chinese physicists used a nuclear magnetic resonance quantum computer with 4 qubits to factor the number 143 (11 x 13), the largest quantum factorization ever performed. Now a <http://arxiv.org/abs/1411.6758>pair of mathematicians say the technique used by the Chinese team is more powerful than originally thought. Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. So instead of just factoring 143, <https://medium.com/the-physics-arxiv-blog/the-mathematical-trick-that-helped-smash-the-record-for-the-largest-number-ever-factorised-by-a-77fde88499>the Chinese team actually quantum factored the number 56153 (233 x 241, which differ by two bits when written in binary). That's the largest quantum factorization by some margin. The mathematicians point out that their discovery will not help code breakers since they'd need to know in advance that the factors differ by 2 bits, which seems unlikely. What's more, the technique relies on only 4 qubits and so can be easily reproduced on a classical computer.
--- co-chair http://ocjug.com/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________ The message was checked by ESET Smart Security. http://www.eset.com
I don't know how you can fairly call that a quantum algorithm -- it can't even store the whole number. By Holevo's theorem it would take 20 qubits to store that number... Charles Greathouse Analyst/Programmer Case Western Reserve University On Wed, Dec 3, 2014 at 12:47 PM, Gustavus Simmons <gsimmons30@comcast.net> wrote:
Something seems odd in the cited article. It says
"Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. "
Without doing any calculation it seems the Fermat prime 65,537 plus 6 times the prime would be a larger example 4,295,491,591 ----- Original Message ----- From: "Ray Tayek" <rtayek@ca.rr.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, December 03, 2014 9:58 AM Subject: [math-fun] Mathematical Trick Helps Smash Record For the Largest Quantum Factorization
http://science-beta.slashdot.org/story/14/12/03/1551239/
mathematical-trick-helps-smash-record-for-the-largest- quantum-factorization
<http://beta.slashdot.org/%7ESoulskill>Soulskill posted about an hour ago | from the still-slower-than-a-12-year-old dept.
<http://beta.slashdot.org/index2.pl?fhfilter=math> Math
<http://beta.slashdot.org/index2.pl?fhfilter=math> < http://science-beta.slashdot.org/story/14/12/03/1551239/ mathematical-trick-helps-smash-record-for-the-largest- quantum-factorization>16
<http://beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: One of the big applications for quantum computers is finding the prime factors of large numbers, a technique that can help break most modern cryptographic codes. Back in 2012, a team of Chinese physicists used a nuclear magnetic resonance quantum computer with 4 qubits to factor the number 143 (11 x 13), the largest quantum factorization ever performed. Now a < http://arxiv.org/abs/1411.6758>pair of mathematicians say the technique used by the Chinese team is more powerful than originally thought. Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. So instead of just factoring 143, <https://medium.com/the- physics-arxiv-blog/the-mathematical-trick-that- helped-smash-the-record-for-the-largest-number-ever- factorised-by-a-77fde88499>the Chinese team actually quantum factored the number 56153 (233 x 241, which differ by two bits when written in binary). That's the largest quantum factorization by some margin. The mathematicians point out that their discovery will not help code breakers since they'd need to know in advance that the factors differ by 2 bits, which seems unlikely. What's more, the technique relies on only 4 qubits and so can be easily reproduced on a classical computer.
--- co-chair http://ocjug.com/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I thought the comment was about primes that differ by two bits which I am sure are not rare. The example I gave was the easist I could come up with without doing any computation. ----- Original Message ----- From: "Charles Greathouse" <charles.greathouse@case.edu> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, December 03, 2014 11:33 AM Subject: Re: [math-fun] Mathematical Trick Helps Smash Record For the Largest Quantum Factorization
I don't know how you can fairly call that a quantum algorithm -- it can't even store the whole number. By Holevo's theorem it would take 20 qubits to store that number...
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Wed, Dec 3, 2014 at 12:47 PM, Gustavus Simmons <gsimmons30@comcast.net> wrote:
Something seems odd in the cited article. It says
"Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. "
Without doing any calculation it seems the Fermat prime 65,537 plus 6 times the prime would be a larger example 4,295,491,591 ----- Original Message ----- From: "Ray Tayek" <rtayek@ca.rr.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, December 03, 2014 9:58 AM Subject: [math-fun] Mathematical Trick Helps Smash Record For the Largest Quantum Factorization
http://science-beta.slashdot.org/story/14/12/03/1551239/
mathematical-trick-helps-smash-record-for-the-largest- quantum-factorization
<http://beta.slashdot.org/%7ESoulskill>Soulskill posted about an hour ago | from the still-slower-than-a-12-year-old dept.
<http://beta.slashdot.org/index2.pl?fhfilter=math> Math
<http://beta.slashdot.org/index2.pl?fhfilter=math> < http://science-beta.slashdot.org/story/14/12/03/1551239/ mathematical-trick-helps-smash-record-for-the-largest- quantum-factorization>16
<http://beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: One of the big applications for quantum computers is finding the prime factors of large numbers, a technique that can help break most modern cryptographic codes. Back in 2012, a team of Chinese physicists used a nuclear magnetic resonance quantum computer with 4 qubits to factor the number 143 (11 x 13), the largest quantum factorization ever performed. Now a < http://arxiv.org/abs/1411.6758>pair of mathematicians say the technique used by the Chinese team is more powerful than originally thought. Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. So instead of just factoring 143, <https://medium.com/the- physics-arxiv-blog/the-mathematical-trick-that- helped-smash-the-record-for-the-largest-number-ever- factorised-by-a-77fde88499>the Chinese team actually quantum factored the number 56153 (233 x 241, which differ by two bits when written in binary). That's the largest quantum factorization by some margin. The mathematicians point out that their discovery will not help code breakers since they'd need to know in advance that the factors differ by 2 bits, which seems unlikely. What's more, the technique relies on only 4 qubits and so can be easily reproduced on a classical computer.
--- co-chair http://ocjug.com/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________ The message was checked by ESET Smart Security. http://www.eset.com
Most of the examples offered so far are easy to factor with Fermat's Difference-of-Squares method. Suppose the target is N. Begin by setting X = ceiling[sqrtN]. Test if X^2-N is a square, say Y^2. If so, then N = X^2 - Y^2 = (X-Y)(X+Y). If not, increment X and loop back to try again. For N=56153, X=237, X^2-N=16, Y=4, N=233*241. For the example in the concluding paragraph of the paper, N=291311, X=540, X^2-N=289, Y=17, N=523*557. When the difference between the factors is less than 2.8 N^1/4, the first X works, and there's no need to loop back for a second try. It's quite remarkable to see a factoring machine operate with less memory than is required to store the problem. What a Brave New World we live in! Rich ---- Quoting Gustavus Simmons <gsimmons30@comcast.net>:
I thought the comment was about primes that differ by two bits which I am sure are not rare. The example I gave was the easist I could come up with without doing any computation. ----- Original Message ----- From: "Charles Greathouse" <charles.greathouse@case.edu> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, December 03, 2014 11:33 AM Subject: Re: [math-fun] Mathematical Trick Helps Smash Record For the Largest Quantum Factorization
I don't know how you can fairly call that a quantum algorithm -- it can't even store the whole number. By Holevo's theorem it would take 20 qubits to store that number...
Charles Greathouse Analyst/Programmer Case Western Reserve University
On Wed, Dec 3, 2014 at 12:47 PM, Gustavus Simmons <gsimmons30@comcast.net> wrote:
Something seems odd in the cited article. It says
"Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. "
Without doing any calculation it seems the Fermat prime 65,537 plus 6 times the prime would be a larger example 4,295,491,591 ----- Original Message ----- From: "Ray Tayek" <rtayek@ca.rr.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, December 03, 2014 9:58 AM Subject: [math-fun] Mathematical Trick Helps Smash Record For the Largest Quantum Factorization
http://science-beta.slashdot.org/story/14/12/03/1551239/
mathematical-trick-helps-smash-record-for-the-largest- quantum-factorization
<http://beta.slashdot.org/%7ESoulskill>Soulskill posted about an hour ago | from the still-slower-than-a-12-year-old dept.
<http://beta.slashdot.org/index2.pl?fhfilter=math> Math
<http://beta.slashdot.org/index2.pl?fhfilter=math> < http://science-beta.slashdot.org/story/14/12/03/1551239/ mathematical-trick-helps-smash-record-for-the-largest- quantum-factorization>16
<http://beta.slashdot.org/%7EKentuckyFC>KentuckyFC writes: One of the big applications for quantum computers is finding the prime factors of large numbers, a technique that can help break most modern cryptographic codes. Back in 2012, a team of Chinese physicists used a nuclear magnetic resonance quantum computer with 4 qubits to factor the number 143 (11 x 13), the largest quantum factorization ever performed. Now a < http://arxiv.org/abs/1411.6758>pair of mathematicians say the technique used by the Chinese team is more powerful than originally thought. Their approach is to show that the same quantum algorithm factors an entire class of numbers with factors that differ by 2 bits (like 11 and 13). They've already discovered various examples of these numbers, the largest so far being 56153. So instead of just factoring 143, <https://medium.com/the- physics-arxiv-blog/the-mathematical-trick-that- helped-smash-the-record-for-the-largest-number-ever- factorised-by-a-77fde88499>the Chinese team actually quantum factored the number 56153 (233 x 241, which differ by two bits when written in binary). That's the largest quantum factorization by some margin. The mathematicians point out that their discovery will not help code breakers since they'd need to know in advance that the factors differ by 2 bits, which seems unlikely. What's more, the technique relies on only 4 qubits and so can be easily reproduced on a classical computer.
--- co-chair http://ocjug.com/
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
__________ Information from ESET Smart Security, version of virus signature database 10820 (20141203) __________
The message was checked by ESET Smart Security.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Charles Greathouse -
Gustavus Simmons -
Ray Tayek -
rcs＠xmission.com