mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-10-26, 19:36   #23
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by ewmayer
Wuss.
Maybe. But Citrix explicitly asked for having that changed back, and I think the thread starter ought to have a say in how the thread should be titled...

Alex
akruppa is offline   Reply With Quote
Old 2006-10-22, 14:47   #24
crandles
 

53×163 Posts
Default

I gather the next number after 15 that could be factored is 21.

I have heard of a quantum computer with 12 qubits with a claim this is the highest so far. How many qubits are needed to factor 21? If this is 12 or less has anyone done it?
  Reply With Quote
Old 2006-11-18, 17:03   #25
proctor
 

186716 Posts
Default A good reason shors is useless.

O.k., so it requires 2N- 1 Qbits to work...
Humm... Factoring a useful number (like rsa 1024) Would then require 2 * 2 ^ 1024 - 1 qbits.
Correct me if i'm wrong, but if each atom could represent 1 qbit, there would still not be enough atoms in the universe for that.
Let's say, on a more reasonable level, that every atom in that little IBM computer could be a qbit. That would make a billion billion (2^64) qbit computer. Which means it could find factors up to 2^63 - 1.
A problem that can be done in under 1 second using trial division.

See, the problem is that the complexity of the computer needed grows in linear time. The quantum computer actually needed to factor large numbers would be larger than the entirety of creation.
  Reply With Quote
Old 2006-11-19, 23:30   #26
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Wrong, it needs (at least) 2N-1 qubits to factor a number of N bits, so for RSA1024 the number of qubits would be (idealized) 2047. Due to technical difficulties, the number of qubits needed will be larger than than, but still a relatively small multiple of N.

Alex
akruppa is offline   Reply With Quote
Old 2006-11-26, 00:03   #27
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

249510 Posts
Default

It seems that researchers have been making quite some progress on developing quantum computers, as seen here. :)

Last fiddled with by ixfd64 on 2006-11-26 at 00:04
ixfd64 is online now   Reply With Quote
Old 2008-07-27, 12:10   #28
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

23518 Posts
Default (1) I need more details about the Shor's algorithm

Quote:
Originally Posted by R.D. Silverman View Post
Shor's algorithm is correct and it works. 15 has indeed been factored on a
4-qubit quantum computer.
I want to know more about the Shor's algorithm.
I know that it is in the complexity class BQP, i.e. quantum polynomial time algorithm.

How long does it take so to factor a GNFS 100 or a GNFS 150 on a quantum computer (whose speed is compatible to that of a Pentium 4 or a Core 2 Duo) by using the Shor's algorithm?

A GNFS 120 takes about 5 days on a Pentium 4 at 2.8 GHz, and that
Core 2 Duo is four times faster than a Pentium 4 processor.

Last fiddled with by Raman on 2008-07-27 at 13:04 Reason: up only so
Raman is offline   Reply With Quote
Old 2008-07-27, 13:00   #29
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default (2) Something is wrong with the AKS algorithm?

I have read that the AKS algorithm is a deterministic polynomial time algorithm to test the primality of a number, that had been discovered by 3 IIT Kanpur students in August 2002.

The paper was being entitled as 'PRIMES IS IN P', a suitable title, indeed, where P is the complexity class, i.e. deterministic polynomial-time.

The condition is being written as
p is prime if and only if
(x-a)p=(xp-a) mod p

Now that let p be a Carmichael number, for example 561

On the left hand side, since p is a Carmichael number,
(x-a)p mod p = (x-a)

On the right hand side, xp mod p = x
so, (xp-a) mod p = (x-a)

So, this algorithm holds so well (LHS = RHS) for all the Carmichael Numbers, which is not at all valid!
Please clarify it up to me

Last fiddled with by Raman on 2008-07-27 at 13:24 Reason: that, which was being.
Raman is offline   Reply With Quote
Old 2008-07-27, 14:56   #30
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

2·73·17 Posts
Default

Quote:
Originally Posted by Raman View Post
I want to know more about the Shor's algorithm.
I know that it is in the complexity class BQP, i.e. quantum polynomial time algorithm.

How long does it take so to factor a GNFS 100 or a GNFS 150 on a quantum computer (whose speed is compatible to that of a Pentium 4 or a Core 2 Duo) by using the Shor's algorithm?

A GNFS 120 takes about 5 days on a Pentium 4 at 2.8 GHz, and that
Core 2 Duo is four times faster than a Pentium 4 processor.
We don't know.

Factoring a 400-bit integer will require a quantum machine with around a thousand qubits (at least 799 and probably more) and we've no real idea how to build one or how fast it will work. The state of the art at the moment is factoring a 4-bit number.

Your question is, in some sense, equivalent to asking how long it would take to factor a 15,000 digit number. For this question, other than "a long time" we just don't know.


Paul

Last fiddled with by xilman on 2008-07-27 at 14:56
xilman is online now   Reply With Quote
Old 2008-07-27, 14:58   #31
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

32×5×79 Posts
Default

Quote:
Originally Posted by Raman View Post
How long does it take so to factor a GNFS 100 or a GNFS 150 on a quantum computer (whose speed is compatible to that of a Pentium 4 or a Core 2 Duo) by using the Shor's algorithm?
A quantum factoring algorithm has an exponential running time until you build a quantum computer big enough to run it on your desired input. With Shor's algorithm we are very far from being able to do that, for RSA numbers of nontrivial size.

More background reading here
jasonp is offline   Reply With Quote
Old 2008-07-28, 10:33   #32
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

4E916 Posts
Default

Quote:
Originally Posted by xilman View Post
Factoring a 400-bit integer will require a quantum machine with around a thousand qubits (at least 799 and probably more) and we've no real idea how to build one or how fast it will work. The state of the art at the moment is factoring a 4-bit number.
Ok, fine. I understand the current situation of the Shor's algorithm.

But, what about the AKS algorithm. Did both of you skip up reading about it?
It is used to prove, i.e. confirm the primality of any given number.

Is the condition really this one?
p is prime if and only if
(x-a)p = (xp-a) mod p

If yes, it holds good so for all the Carmichael Numbers, whereas it shouldn't if it were a primality proving algorithm.

Last fiddled with by Raman on 2008-07-28 at 10:39
Raman is offline   Reply With Quote
Old 2008-07-28, 11:46   #33
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,733 Posts
Default

Quote:
Originally Posted by Raman View Post

But, what about the AKS algorithm. Did both of you skip up reading about it?


Well, I'm pretty sure jasonp has done his homework w.r.t AKS: http://images.apple.com/acg/pdf/aks3.pdf
bsquared is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Alternatively-gifted factoring algorithm Prime95 Miscellaneous Math 72 2015-10-26 00:14
Shor's Algorithm flouran Math 3 2009-10-27 09:31
Prime Factoring Algorithm Visu Math 66 2008-05-12 13:55
Faster Factoring Algorithm? Citrix Factoring 6 2007-12-23 11:36
A new prime factoring algorithm? Visu Factoring 22 2006-11-09 10:43

All times are UTC. The time now is 10:02.


Mon Feb 6 10:02:03 UTC 2023 up 172 days, 7:30, 1 user, load averages: 1.27, 1.12, 1.01

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”