0 Members and 1 Guest are viewing this topic.

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

I'm not sure if this can be generalized to higher moduli. If it can, it might not be pretty.

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)=16xy^{2}+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.