New RSA Algorithm discussion

[DJ Omnimaga]

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...

[Builderboy]

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]

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.

[DJ Omnimaga]

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.

[Lionel Debroux]

Quoting myself from reply #71 in this very topic:

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://www.omnimaga.org/index.php?topic=3639.0

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.

[t0xic_kitt3n]

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.

[graphmastur]

We all know complexity of it.  I know it very well in fact.  We're actually pretty much hoping to get lucky here. ;-)

[SirCmpwn]

I think we need to move away from the arguments about the infeasibility of this and move on to making it happen.

[DJ Omnimaga]

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.

[willrandship]

Yay for that.

[Tribal]

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 All | Copy To Clipboard

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

: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'.

[willrandship]

theoretically, we don't have to find a way to solve all semiprimes, just one
hmmmm

[DJ Omnimaga]

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 All | Copy To Clipboard

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

: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.

[graphmastur]

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?

[Tribal]

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?

I was randomly throwing a prime in P and Q, so I didn't know which was smaller.
In these scenarios I am using a known P and Q only to generate a semiprime N. From that, I'm trying to find a formula that would give the amount of numbers away from what might be the factor of N(I'm not actually using P or Q for anything except to get N and to stop after I've reached the lower of the two). With this function, it may speed up any TF'ing because you are not checking every other number, you would be checking the number given by the function. I believe that the function is uniform to all semiprimes as well, because the graph given for a random semiprime is equivalent if not the same for all of them. I'm not exactly sure how to find this function though, that's where I'm stuck at. It is a exponential graph that has multiple asymptotes, but from that I don't know what todo