Finding the first primitive root of a number over 100,000,000

Question

Here is my code:

  import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.security.SecureRandom;

public class Solution {
    static BigDecimal result;
    static Double y = 0.0;
    static int o;
    static int[] factors = new int[1];
    static int current = 0;
    public static void main(String[] args) {
        Scanner a1 = new Scanner(System.in);
        int b = a1.nextInt();
        o = b;
        result = new BigDecimal(Integer.valueOf(b));
        BigInteger N = new BigInteger(Integer.toString(b - 1));
        factor(N);
        boolean isPrimitive = true;

        for (int i1 = 2; i1 < 10000;i1++) {
        isPrimitive = true;
        //System.out.println("Enter the value of a large prime no");
        BigInteger value = new BigInteger(String.valueOf(o-1));
        //System.out.println("\nEnter the value of alpha");
        BigInteger checking = new BigInteger(String.valueOf(i1));
        BigInteger bigValue = new BigInteger(String.valueOf(o));

        for(int i=0;i<factors.length;i++)
        {
            BigInteger temp = checking.pow(factors[i]);
           // System.out.println("checking "+i1+": "+temp+" mod "+o+" = " + (temp.mod(new BigInteger(String.valueOf(o)))));
         if ((temp.mod(bigValue)).equals(BigInteger.ONE)) {
             isPrimitive = false;
             break;
         }
        }
        if(isPrimitive) {
            System.out.print(i1+" ");
            break;
        }
        else{
            //System.out.println("not primitive roots");
        }

        }
        System.out.println(result.toBigInteger());


    }



    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE = new BigInteger("1");
    private final static BigInteger TWO = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();

    public static BigInteger rho(BigInteger N) {
        BigInteger divisor;
        BigInteger c = new BigInteger(N.bitLength(), random);
        BigInteger x = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        // check divisibility by 2
        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

        do {
            x = x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while ((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    public static void factor(BigInteger N) {

        //System.out.println("result = "+result);
        if (N.compareTo(ONE) == 0) return;
        if (N.isProbablePrime(20)) {
           // System.out.println("n = "+N);
            if ((N.doubleValue() != (y)) &&N.doubleValue() != (1.0) ) {
                // System.out.println("j = "+String.valueOf(1.0 - (1.0/(N.doubleValue()))));
                BigDecimal j = new BigDecimal(String.valueOf(1.0 - (1.0/(N.doubleValue()))));
                //System.out.println("result = " +result+" * "+j);
                result = new BigDecimal(String.valueOf(result.doubleValue() * j.doubleValue()));
                //System.out.println(result.multiply(j));

                //System.out.println((String.valueOf(1.0 - (1.0/(N.doubleValue())))));

                y = N.doubleValue();
                if (current == factors.length) {
                    int[] temp = new int[factors.length+1]; 
                    for (int i = 0; i < factors.length;i++) {
                        temp[i] = factors[i];
                    }
                    factors = temp;

                }
                factors[current] = o/y.intValue();
               // System.out.println(o+"/"+y.intValue());
                current++;


                //System.out.println("result = "+result);
            }

            return;
        }
        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }



}

I am trying to find the first primitive root of a prime number, then the amount of primitive roots it has. Finding the amount is no problem for any number, but finding the first number is supposed to work for any number up to 1 billion on a certain system for on which other people have been successful. It works for all values up to around a million, but it doesn't work for 999994267. I don't know how I can possibly optimize this further. I have spent maybe 18 hours on this. I honestly can't figure this out. Any suggestions?

Math Explanation: It takes the factors of the given number o, and tests every number from 2 if it's o/factor[1,2,...] is = 1, if none of o's factors are, it breaks and prints the number.

PS. It is possible, as many other people have done it on the same system.

What do you mean "but it doesen't work for 999994267". What happens? — Carcigenicate, Jan 02 '17 at 20:27
@Arseniy If this is purely an optimization request, this should be on Code Review since this code doesn't appear to be broken, just too slow — Carcigenicate, Jan 02 '17 at 20:30
It is supposed to work on a certain system, which gives me a timeout. — Arseniy, Jan 02 '17 at 20:31
@Arseniy That would be valuable information to add to your question. — Modus Tollens, Jan 02 '17 at 20:32
At least, post us a link explaining the Maths or explain it yourself please. — Pascal Heraud, Jan 02 '17 at 20:32
You keep creating unnecessary `BigInteger` instances. `new BigInteger(String.valueOf(1))` is definitely unnecessary (use `ONE` instead); and `new BigInteger(String.valueOf(o))` can be calculated outside the loop. — Andy Turner, Jan 02 '17 at 21:24
Do you have to use `BigInteger` classes at all? How big numbers should you be able to handle? — Igor Nikolaev, Jan 02 '17 at 22:07
I tried substituting `BigInteger.pow` with exponentiation by squaring from this answer (http://stackoverflow.com/a/101613/530351) and it seems to solve the issue, though I didn't check the correctness of the result. — Igor Nikolaev, Jan 02 '17 at 22:09
@IgorNikolaev well, what if i have 761, and I need to test if 2^380 is a primitive root, an integer can't handle 2^380, right? — Arseniy, Jan 02 '17 at 22:10
That's true, but you mentioned your program couldn't handle even smaller numbers, so I assumed you don't need to. — Igor Nikolaev, Jan 02 '17 at 22:12
"It works for all values up to around a million, but it doesn't work for 999994267" — Arseniy, Jan 02 '17 at 22:13
Also I'm not quite sure what primitive root is. Is this the same? https://en.wikipedia.org/wiki/Primitive_root_modulo_n — Igor Nikolaev, Jan 02 '17 at 22:14
@IgorNikolaev Yes, it's the same. Am working on understanding exponentiation by squaring and implementing it in my code. Hope it works! (Thanks for the info, btw.) — Arseniy, Jan 02 '17 at 22:19
Also, if you need to check this condition: `2^380 ≡ 1 mod 761`, then you should look into modular arithmetic. In that case you don't need to evaluate `2^380` at all. These links might be helpful to start: https://en.wikipedia.org/wiki/Modular_arithmetic https://en.wikipedia.org/wiki/Modular_exponentiation — Igor Nikolaev, Jan 02 '17 at 22:22

score -1 · Answer 1 · answered Jan 05 '17 at 13:28

Ok so thanks to @IgorNikolaev above in the comments of my question I have figured out my problem and solved it. To fully optimize a modPow operation you need to use modular arithmetic.

Here are some links he provided which greatly helped:

en.wikipedia.org/wiki/Modular_arithmetic

en.wikipedia.org/wiki/Modular_exponentiation

And here is the code I wrote based on those links:

private static BigInteger fastModPow(BigInteger base, BigInteger exponent, final BigInteger modulo) {

    BigInteger result = BigInteger.ONE;
    while (exponent.compareTo(BigInteger.ZERO) > 0) {
        if (exponent.testBit(0)) 
            result = (result.multiply(base)).mod(modulo);
        exponent = exponent.shiftRight(1);
        base = (base.multiply(base)).mod(modulo);
    }
    return result.mod(modulo);
}

As you will see in the first link, it sort-of "wraps around" to find the mod of a power.

Thanks for everyones help.

This is pointless as the modPow is already a BigInteger method and is called, wait for it, ... [`modPow`](https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/math/BigInteger.html#modPow(java.math.BigInteger,java.math.BigInteger)) — President James K. Polk, Feb 01 '22 at 11:05

Finding the first primitive root of a number over 100,000,000

1 Answers1