# [libmath-prime-util-perl] 20/55: Speedup for znprimroot

```This is an automated email from the git hooks/post-receive script.

ppm-guest pushed a commit to annotated tag v0.41
in repository libmath-prime-util-perl.```
```
commit d51a718dd512fd0fe85ce8301302c6aedc092421
Author: Dana Jacobsen <d...@acm.org>
Date:   Fri May 2 16:13:28 2014 -0700

Speedup for znprimroot
---
util.c | 20 +++++++-------------
1 file changed, 7 insertions(+), 13 deletions(-)

diff --git a/util.c b/util.c
--- a/util.c
+++ b/util.c
@@ -1460,19 +1460,13 @@ UV znprimroot(UV n) {
if (n % 4 == 0)  return 0;
if (is_prob_prime(n)) {
phi = n-1;
-  } else {  /* Calculate Totient and Carmichael Lambda at same time */
-    UV lambda = 1;
-    nfactors = factor_exp(n, fac, exp);
-    phi = 1;
-    for (i = 0; i < nfactors; i++) {
-      UV pk = fac[i]-1;
-      for (j = 1; j < exp[i]; j++)
-        pk *= fac[i];
-      phi *= pk;
-      if (i == 0 && fac[0] == 2 && exp[0] > 2)  pk >>= 1;
-      lambda = lcm_ui(lambda, pk);
-    }
-    if (phi != lambda) return 0; /* prim root exists only if phi(n) = CL(n) */
+  } else {  /* prim root exists if n is 2, 4, p^a, or 2(p^a) for odd prime p */
+    if (n & 0x3) nfactors = factor_exp( (n&1) ? n : n>>1, fac, exp);
+    else         nfactors = 0;
+    if (nfactors != 1) return 0;
+    phi = fac[0]-1;  /* n = p^a for odd prime p.  Calculate totient. */
+    for (i = 1; i < exp[0]; i++)
+      phi *= fac[0];
}
nfactors = factor_exp(phi, fac, exp);
for (i = 0; i < nfactors; i++)

--
Alioth's /usr/local/bin/git-commit-notice on
/srv/git.debian.org/git/pkg-perl/packages/libmath-prime-util-perl.git

_______________________________________________
Pkg-perl-cvs-commits mailing list
Pkg-perl-cvs-commits@lists.alioth.debian.org
http://lists.alioth.debian.org/cgi-bin/mailman/listinfo/pkg-perl-cvs-commits
```