Group theory within Cryptography regarding order of elements in a group of integers Z*p

I was kinda thrown in the deep end into group theory and i am a bit lost for a Cryptography class i have. Basically a practical i开发者_JAVA技巧 have to implement in java is,

order(prime number, list of factors of p-1 , any a)

This should return the order of a in the group Z*p, where f is a list of prime factors of p-1. Ensure that your method works when f contains duplicates. For example, consider cases where p=17

Here is what i have so far , (taken from steps within my notes)

public static BigInteger order(BigInteger p, List<BigInteger> f, BigInteger a){
    //Algorithm starts like this
    //Start by setting t equal to p-1 i.e t= p1 p2...pn
    BigInteger t = p.subtract(BigInteger.ONE);
    for(BigInteger pi : f){
        //test if a^t1 = 1 mod p where t1 = t/pi
        BigInteger t1 = t.divide(pi);

        if(Practical5ExponentiationModMSquareAndMultiply.expm(p, a, t1).equals(BigInteger.ONE)){
            t = t1;
            System.out.println("t after mod = "+t);
            System.out.println("pi after mod = "+pi);
        }
    }       
    return t;

}

the list of prime factors f is generated by another method and then passed in

The notes i have are quite difficult to understand and i was wondering if any could tell me what i should actually be returning. Also could u give me a possible understanding of this snippet of group theory as it could help with my further practicals

---

You are looking for the smallest number o such that a^o == 1 (mod p), i.e. the smallest o such that p divides a^o - 1.

The group theory results you need is that the multiplicative group of integers mod p is cyclic of order p-1. This means that:

• The order o divides p-1 and satisfies a^o == 1 (mod p)
• The order o is the smallest number which satisfies the preceding condition.

Thus you can find the order by taking the prime factors of p-1, and repeatedly dividing p-1 by them until it's no longer true that p divides a^n - 1.

Example 1: p = 13, p-1 = 2*2*3, a = 5.

For p = 2, 5^(12/2) == 12 (mod 13), so you can't lose the 2s in the order.

For p = 3, 5^(12/3) == 1 (mod 13), so you can lose the 3 in the order.

Thus the order is 2*2 = 4.

The example given to you (p = 17) is another illustrative case:

Example 2: p = 17, p-1 = 2*2*2*2, a = 9

9^(16/2) == 1 (mod 17), so you can lose the first 2.

9^(16/4) == 16 (mod 17), so you can't lose the second 2, and you can stop searching.

Thus the order is 2*2*2 = 8.

Hopefully this should be enough for you to see the algorithm.