mpz_set_str() question

[Joerg Arndt]

Isn't it possible to do the Miller-Rabin thing with some
nonresidues and observe whether you get sqrt(-1) at
the final squarings?  Once you start with a primitive root
(which is not terrible unlikely even with just random start
values) you *will* catch sqrt(-1).

Best regards,   jj


* hermann at stamm-wilbrandt.de <hermann at stamm-wilbrandt.de> [Feb 29. 2024 16:49]:
> On 2024-02-23 14:00, niXman's Github wrote:
> > ...
> > in the process of studying the implementation of those functions I
> > paid attention to the most obvious reasons slowing down parsing:
> > 0) calls to `strlen()`/`strchr()` etc functions.
> > 1) memory allocations and copying into, just to add the final '\0'
> > char. (mpq_set_str)
> > 2) preliminary memory allocations and copying into char-by-char just
> > to full processing the input string. (mpz_set_str/mpf_set_str)
> > 
> > let me explain with the simplest example on the `mpz_set_str()`
> > function:
> > ...
> > 
> Hi,
> 
> yesterday 8.55 day 16 thread forced on chiplet0 of AMD 7950X CPU patched
> LLR 4.0.5 software based on gwnum lib did compute sqrt(-1) (mod p) for
> largest known prime p =1 (mod 4) known since 9/2023.
> 
> Today I added validation code for Python, Node and C++ in addition to
> PARI/GP.
> You might want to use 7462826 hexadecimal digits sqrt(-1) (mod p) in
> sqrtm1.gp file:
> https://github.com/Hermann-SW/RSA_numbers_factored/tree/main/llr/11%2C981%2C518#855-days-computation
> 
> hermann at 7950x:~/RSA_numbers_factored/llr/11,981,518$ make validate
> g++ -O3 validate.cc -lgmpxx -lgmp -o validate.cc.out
> ./validate.cc.out
> 11981518 decimal digits prime p
> 0.008523s for mpz_set_str() of 7462826 hexadecimal digits sqrt(-1) (mod p)
> 1.56775s for computing powm(_, sqrtm1, 2, p)
> 1 (sqrtm1*sqrtm1 % p == p-1)
> 0.00625s for mpz_set_str() of x and y
> 1 (x*x + y*y == p)
> hermann at 7950x:~/RSA_numbers_factored/llr/11,981,518$
> 
> 
> Regards,
> 
> Hermann.
> 
> _______________________________________________
> gmp-discuss mailing list
> gmp-discuss at gmplib.org
> https://gmplib.org/mailman/listinfo/gmp-discuss