﻿ New RSA Algorithm discussion
23 May, 2013, 13:21:00
 OmnomIRC You must Register, be logged in and have at least 40 posts to use this shout-box! If it still doesn't show up afterward, it might be that OmnomIRC is disabled for your group or under maintenance.Note: You can also use an IRC client like mIRC, X-Chat or Mibbit to connect to an EFnet server and #omnimaga.

 Pages: [1] 2 3 ... 14   Go Down
 Author Topic: New RSA Algorithm discussion -  (Read 12790 times) 0 Members and 1 Guest are viewing this topic.
bwang
LV7 Elite (Next: 700)

Offline

Last Login: 11 August, 2012, 12:59:06
Date Registered: 20 June, 2009, 01:42:58
Posts: 632

Total Post Ratings: +19

 « on: 22 July, 2010, 04:45:26 » 0

the reason we need to factor n into p*q is so that we can calculate phi(n)=(p-1)*(q-1), right? well, what if, instead of trying to find a better factoring algorithm, we try to find a fast way to compute the totient without knowing the factors.....
No. Computing phi(n) is polynomial-time equivalent to factoring n. It is generally accepted that the two problems are equally hard.
Okay, well take any n which is a semiprime and do mod 4 of it.  eg, the remainder when it is divided by 4.  So if I have p=13 and q=19, that means p mod 4=1 and q mod 4=3, so pq mod 4=3.  That means that if we have an n, where n mod 4=3, it either means the p mod 4=3 or q mod 4=3, and the other mod 4 =1.

There is one thing I messed up, though.  It is supposed to be (4x+1)(4y+3)=16xy2+12x+4y+3.  I'll go fix that in my last post...  Basically, though, if you solve that over the integers, it yields the factors.  There is only one solution.
Why 16*x*y^2? I think its 16xy.
---------------------------------------------------------------------------------------------------------------------
I believe the factorization of RSA-768 used the NFS. If we were really crazy, we could try writing an implementation of the NFS that is faster than what we currently have (GGNFS + Msieve).
Number field sieves are hard to write It would be an interesting community project, though.
 Logged
 Pages: [1] 2 3 ... 14   Go Up