Re: Why is "lift(Mod(qnr, n)^(n\4))" 16% slower than C libgmp "powm(r, qnr, n/4, n)" ?

[hermann@stamm-wilbrandt.de]

On 2023-07-15 11:08, Bill Allombert wrote:
> Sure, but for some other prime numbers, it seems to be slower than GMP,
> hence my enquiry.
>
> For example, could you try
>
> p=fibonacci(148091); Mod(2,p)^((p-1)/4)
> and
> p=fibonacci(148091); Mod(3,p)^((p-1)/4)
>
> but more importantly, we do not do anything clever.
>
> So I suspect the bit pattern of the exponent to be relevant.
I will look into that later.

What I did is to create a small bit pattern inspector.
Does show that exponent ((p-1)\4) has no big groups of contiguous 1s or 
0s:

hermann@7600x:~$ gp -q < bitpattern.gp
13: [2, 1, 1]
170: [1, 1, 1, 1, 1, 1, 1, 1]
204: [2, 2, 2, 2]
30949-digit p
102808-bit exponent
51526 1-bits
  ***   last result computed in 5,960 ms.
51324 contiguous bit groups
bit groups of length >12: [13, 13, 15, 14, 13, 13, 13, 13, 16, 19, 13]
hermann@7600x:~$
hermann@7600x:~$ cat bitpattern.gp

bitpattern(n) = {
  p=[];
  while(n!=0, \
    z = valuation(n, 2); \
    n = shift(n, -z); \
    o = valuation(n+1, 2); \
    n = shift(n, -o); \
    p = concat([o, z], p); \
  );
  l=#p;
  if(p[l]==0, p=p[1..l-1]);
  p
};

print(13, ": ", bitpattern(13));
print(170, ": ", bitpattern(170));
print(204, ": ", bitpattern(204));

p=fibonacci(148091);
print(#digits(p), "-digit p");
e=(p-1)\4;
print(#binary(e), "-bit exponent");
print(vecsum(binary(e)), " 1-bits");
a=bitpattern(e);
##
print(#a, " contiguous bit groups");
b=[];
foreach(a,x,if(x>12, b=concat(b,x)));
print("bit groups of length >12: ", b);
hermann@7600x:~$


Regards,

Hermann.