Re: Euler's Totient function - a question on efficient implementation

[hermann@stamm-wilbrandt.de]

On 2024-11-07 00:33, American Citizen wrote:
> Is there a way to find a very efficient implementation?
Unlikely, since to my knowledge prime factorization is needed.
Knowing the prime factorization, eulerphi() can be computed easily.

Because of that I made use of the known prime factors of RSA numbers
up to RSA-250 to provide fast eulerphi() function for all
factored sofar RSA-numbers (name totient()):
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/RSA_numbers_factored.gp#L1538

I did factor all prime factors of the two primes of factored sofar
RSA numbers up to RSA-250 as well. With those stored factorizations
totient_2() function efficiently computes eulerphi(eulerphi(RSA(n)):
https://github.com/Hermann-SW/RSA_numbers_factored/blob/main/pari/RSA_numbers_factored.gp#L1564

Longest p-1/q-1 factorization time was 2:04:25h on AMD 7600X CPU
with cado-nfs for 125 decimal digit number p-1 of RSA-250:
https://github.com/Hermann-SW/RSA_numbers_factored/tree/main/cado-nfs#factoring-rsa-p-1-and-q-1


Demonstration for RSA-250:

hermann@j4105:~/RSA_numbers_factored/pari$ gp -q RSA_numbers_factored.gp
? RSA.totient(250)
2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687298754604485313310619754320029186553180340912603879017884504312838403856515485700993615480396424774279472227006542299206581860
? ##
  ***   last result: cpu time 0 ms, real time 0 ms.
? RSA.totient_2(250)
395136794910030187860355609218180836939268526375462071074975591196960885990594619369136835990465005441467706458771729477855393275547633363830725250560151913018519292550630474961421525032851167115483071112495553074081802134497566998641211400209825792
? ##
  ***   last result: cpu time 0 ms, real time 1 ms.
?


Regards,

Hermann.