Prev: Method and Logic
Next: Frustration with mathematics
From: Rainer Urian on 5 Feb 2010 12:50
Here is the algortithm as a PARI script:

Exp2Crt(n,e,d)=
{
local (a,k, found,y,p,q,dp,dq,pinvq);
a=1;
found = 0;
until(found,
a = a+1;
k = (e*d-1);
until(found,
y = Mod(a,n)^k;
if(y == Mod(-1,n), break());
if(y != Mod( 1,n), found=1;break());
if(k % 2 == 1, break());
k = k/2;
);
);
p=gcd(lift(y)-1,n);
q= n/p;
dp= d % (p-1);
dq =d % (q-1);
pinvq = lift(Mod(p^(-1),q));
[p,q,dp,dq,pinvq]
}


"Mok-Kong Shen" <mok-kong.shen(a)t-online.de> schrieb im Newsbeitrag
news:hkgn8h$rko$03$1(a)news.t-online.com...
> Rainer Urian wrote:
>> the problem is that you cannot know if ed-1 is simple to factor.For
>> instance, if p,q are Germain primes (i.e. p'= (p-1)/2 is also prime) then
>> you cannot factor 2*p'*q'. You also cannot know that lcm and phi differ
>> only by a factor of 2.
>> On the other hand, before using an algorithm which needs factoring, it
>> is far more preferable to use a fast probabilistic algorithm.
>
> But a fast probabilistic algorithm on what (not to factor something?) ?
>
> Thanks,
>
> M. K. Shen
>

First  |  Prev  | 
Pages: 1 2 3 4 5
Prev: Method and Logic
Next: Frustration with mathematics