Re: How to do t_INT bit operations?

[hermann@stamm-wilbrandt.de]

On 2023-07-05 21:22, Ruud H.G. van Tol wrote:
> > > Is that the way to do t_INT bit operations in GP?
> > > Are there alternatives more like the C bit operators?
> > ? bit<TAB>
> > bitand        bitnegimply   bitprecision  bitxor
> > bitneg        bitor         bittest
> >
> > You may want to check those functions (except bitprecision)
> >
> > The reference cards are also a good place to look for functions (here 
> > in
> > refcard.pdf, first page, section on "Operators")
>
> Also see: binary(), valuation(), logint().
>
> Examples:
> 1. count trailing 0-bits: valuation(n,2).
> 2. count trailing 1-bits: valuation(n+1,2).
Thanks to both of you, avoided me to go into wrong direction!

cado-nfs.py was able to factor up to RSA-140 really fast, with total 
time divided by
elapsed time >10 on 6C/12T 7600X CPU:
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/cado-nfs/README.md#cado-nfs

I try to parallelize computation of "Mod(qnr, p)^(p\4)" for really big 
primes to make
that computation of "sqrt(-1) (mod p)" faster by utilizing all 12 HW 
threads.

A very first test with splitting exponentiation into 2 and then multiply 
results on slow
Raspberry Pi400 shows that runtime does not get worse by doing so:

pi@pi400-64:~/RSA_numbers_factored/pari $ gp -q split.gp
prime p has
2467 decimal digits length
8193 bits length
5 bits set
526ms
519ms
pi@pi400-64:~/RSA_numbers_factored/pari $


With this split.gp:

assert(b, v, s) = { if(!(b), error(Str(v) Str(s))); }

split(n) = {
  my(l=2^(1+logint(n, 2)), a=[l,l], b=0, c);
  while(n!=0,
    c = 2^valuation(n, 2);
    n = bitxor(n, c);
    a[1+b] = bitxor(a[1+b], c);
    b = !b;
  );
  [bitxor(a[1], l), bitxor(a[2], l)]
}

p = 2 ^ 2 ^ 13 + 897;
\\ p = (10^10000 - 1) \ 3 - 10^6333;

print("prime p has");
print(#digits(p), " decimal digits length");
print(#binary(p), " bits length");
print(vecsum(binary(p)), " bits set");

forprime(t=2,oo,if( kronecker(t, p)==-1, qnr=t; break()));
gettime();
s=lift(Mod(qnr, p)^(p\4));
print(Str(gettime())"ms");

assert(s^2 % p == p-1, "s^2 % p != p-1: ", s);

[a,b]=split(p\4);

gettime();
s1=Mod(qnr, p)^a;
s2=Mod(qnr, p)^b;
s=lift(s1*s2);
print(Str(gettime())"ms");

assert(s^2 % p == p-1, "s^2 % p != p-1: ", s);
\q


Regards,

Hermann.