### Author Topic: New RSA Algorithm discussion  (Read 57811 times)

0 Members and 1 Guest are viewing this topic.

#### DJ Omnimaga

• Clacualters are teh gr33t
• CoT Emeritus
• LV15 Omnimagician (Next: --)
• Posts: 55941
• Rating: +3154/-232
• CodeWalrus founder & retired Omnimaga founder
##### Re: New RSA Algorithm discussion
« Reply #150 on: February 28, 2011, 01:09:48 am »
No, it doesn't need a server, and runs on almost every platform imaginable.  You'll be able to specify your range, and claim it here.
Ah I see what the range was for then. I was wondering how we would avoid duplicates while doing our own thing alone on each side .

I wonder how many years this will take, though...
Dream of Omnimaga

#### Builderboy

• Physics Guru
• CoT Emeritus
• LV13 Extreme Addict (Next: 9001)
• Posts: 5673
• Rating: +613/-9
• Would you kindly?
##### Re: New RSA Algorithm discussion
« Reply #151 on: February 28, 2011, 01:11:29 am »
Expect 500+ guests if they link to omni.

This should be fun.

I'm gonna say don't count your chickens before they hatch So the basic mentality here is that, we know its unlikely, but we are going for it against all odds?  I'm in

#### AngelFish

• Is this my custom title?
• LV12 Extreme Poster (Next: 5000)
• Posts: 3242
• Rating: +270/-27
• I'm a Fishbot
##### Re: New RSA Algorithm discussion
« Reply #152 on: February 28, 2011, 01:11:31 am »
Best case: It'll be solved by tomorrow.

Worst case: The sun will have died by the time the solution is found using this method.
« Last Edit: February 28, 2011, 01:12:00 am by Qwerty.55 »
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

#### DJ Omnimaga

• Clacualters are teh gr33t
• CoT Emeritus
• LV15 Omnimagician (Next: --)
• Posts: 55941
• Rating: +3154/-232
• CodeWalrus founder & retired Omnimaga founder
##### Re: New RSA Algorithm discussion
« Reply #153 on: February 28, 2011, 02:40:04 am »
I think Slashdot and the like mostly post about stuff that has been done, not planned to be done, so it might not work. But otherwise I am not sure of a good way to convince other people to get into the project. It would take thousands and thousands of them, and then there would be a need for a server so we don't have to put like 1000 people in the first post.
Dream of Omnimaga

#### Lionel Debroux

• LV11 Super Veteran (Next: 3000)
• Posts: 2135
• Rating: +290/-45
##### Re: New RSA Algorithm discussion
« Reply #154 on: February 28, 2011, 08:08:58 am »
Quoting myself from reply #71 in this very topic:
Quote
We've already had lots of talk about factoring the key, in another topic (but it's understandable that you missed it: there's lots of activity on the forum, and that is a good thing): http://ourl.ca/6236

I have summarized multiple times how impractical the factorization is (unless some ground-breaking algorithm comes to the rescue, which we should not hold our breath on): basically, three orders of magnitude harder than the state of the art.
A linear extrapolation of the figures given in the paper detailing the factorization of RSA-768, consistent with what we know of 512-bit RSA factoring, gives the need of sifting through 10000-100000 TB (yes, I really mean terabytes) of data, after those have been produced by several dozen thousands of computers running for years (or ten times as many computers, running for one tenth of the time).
This does not, however, mean that we can't spend up to several CPU-years trying to find a factor by Trial Factoring (beyond that would not be reasonable): it's extremely unlikely that we'll succeed by sifting through a search space which represents an vanishingly small part of a particle, compared to the whole universe - but such is the beauty of random.
Member of the TI-Chess Team.
Co-maintainer of GCC4TI (GCC4TI online documentation), TILP and TIEmu.

#### fb39ca4

• LV10 31337 u53r (Next: 2000)
• Posts: 1749
• Rating: +60/-3
##### Re: New RSA Algorithm discussion
« Reply #155 on: February 28, 2011, 04:11:21 pm »
Best case: It'll be solved by tomorrow.

Worst case: The sun will have died by the time the solution is found using this method.
By the time the sun dies out, I'm pretty sure we'll have quantum computers.

#### jnesselr

• King Graphmastur
• LV11 Super Veteran (Next: 3000)
• Posts: 2270
• Rating: +81/-20
• TAO == epic
##### Re: New RSA Algorithm discussion
« Reply #156 on: February 28, 2011, 05:26:02 pm »
We all know complexity of it.  I know it very well in fact.  We're actually pretty much hoping to get lucky here. ;-)

#### SirCmpwn

• Guest
##### Re: New RSA Algorithm discussion
« Reply #157 on: February 28, 2011, 05:38:53 pm »
I think we need to move away from the arguments about the infeasibility of this and move on to making it happen.

#### DJ Omnimaga

• Clacualters are teh gr33t
• CoT Emeritus
• LV15 Omnimagician (Next: --)
• Posts: 55941
• Rating: +3154/-232
• CodeWalrus founder & retired Omnimaga founder
##### Re: New RSA Algorithm discussion
« Reply #158 on: February 28, 2011, 06:14:15 pm »
Yeah to be fair I agree with Sir. Of course later it might be best to move on to more powerful computers and have this run on multiple computers from multiple people, because it's gonna take a friggin long while, but the thing is that in 2004-07, people said a Gameboy emulator for the 84+ was impossible, same for a Mode 7 engine, yet people managed to do it a few years later. Trying stuff is what makes the community progress. Not trying anything because we expect it to not work at all gives a 2008 POTY in long terms.
Dream of Omnimaga

#### willrandship

• Omnimagus of the Multi-Base.
• LV11 Super Veteran (Next: 3000)
• Posts: 2953
• Rating: +98/-13
• Insert sugar to begin programming subroutine.
##### Re: New RSA Algorithm discussion
« Reply #159 on: February 28, 2011, 06:22:01 pm »
Yay for that.

#### Tribal

• The Fallen
• Posts: 218
• Rating: +15/-1
##### Re: New RSA Algorithm discussion
« Reply #160 on: March 07, 2011, 05:34:00 pm »
I've been trying to find some function that could be used to find the next number that *might* be a factor in a semiprime. I've been using this program to get my test data, I can't really explain what it's doing so if someone with more math skill than me and can understand this program, if you would I would appreciate it

Code: [Select]
:PQ→N:1→F:int(√(N→X:{0→L1:L1→L2:For(θ,1,2:While (fPart(N/X)>fPart(N/(X+1)))+(θ=2:If X=Q-1:Return:X-1→X:F+1→F:If θ=2:Then:If X>0:Then:If fPart(N/X)<fPart(N/(X+1:Then:Disp {X,F:If L1(1)=0:Then:{X→L1:{F→L2:Else:X→L1(dim(L1)+1:F→L2(dim(L2)+1:End:X-1→X:1→F:End:End:End:End:X-1→X:End
(not very effective because of the limited memory on the calculator, have to find almost a perfect semiprime to work with. Might try whipping up a C program that can be used to get/graph the data)

EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.
« Last Edit: March 07, 2011, 06:50:13 pm by Tribal »

#### willrandship

• Omnimagus of the Multi-Base.
• LV11 Super Veteran (Next: 3000)
• Posts: 2953
• Rating: +98/-13
• Insert sugar to begin programming subroutine.
##### Re: New RSA Algorithm discussion
« Reply #161 on: March 07, 2011, 05:48:02 pm »
theoretically, we don't have to find a way to solve all semiprimes, just one
hmmmm

#### DJ Omnimaga

• Clacualters are teh gr33t
• CoT Emeritus
• LV15 Omnimagician (Next: --)
• Posts: 55941
• Rating: +3154/-232
• CodeWalrus founder & retired Omnimaga founder
##### Re: New RSA Algorithm discussion
« Reply #162 on: March 07, 2011, 11:46:15 pm »
I've been trying to find some function that could be used to find the next number that *might* be a factor in a semiprime. I've been using this program to get my test data, I can't really explain what it's doing so if someone with more math skill than me and can understand this program, if you would I would appreciate it

Code: [Select]
:PQ→N:1→F:int(√(N→X:{0→L1:L1→L2:For(θ,1,2:While (fPart(N/X)>fPart(N/(X+1)))+(θ=2:If X=Q-1:Return:X-1→X:F+1→F:If θ=2:Then:If X>0:Then:If fPart(N/X)<fPart(N/(X+1:Then:Disp {X,F:If L1(1)=0:Then:{X→L1:{F→L2:Else:X→L1(dim(L1)+1:F→L2(dim(L2)+1:End:X-1→X:1→F:End:End:End:End:X-1→X:End
(not very effective because of the limited memory on the calculator, have to find almost a perfect semiprime to work with. Might try whipping up a C program that can be used to get/graph the data)

EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.
Do you want to factor the TI-Nspire key from a TI calc using TI-BASIC?

j/k interesting.
Dream of Omnimaga

#### jnesselr

• King Graphmastur
• LV11 Super Veteran (Next: 3000)
• Posts: 2270
• Rating: +81/-20
• TAO == epic
##### Re: New RSA Algorithm discussion
« Reply #163 on: March 08, 2011, 07:04:08 am »
EDIT: Right now this program assumes Q is the smaller of the two primes. Just add '(P>Q)Q+(Q>P)P→L' at the beginning and change 'If X=Q-1:Return' to 'If X=L-1:Return'.
usually P is used as the smaller.  And if you already know P or Q, why do we need to find it?

• The Fallen