Primitive Root

2.cpp

/**
 * 	密碼學導論作業二/第二題
 *	@author Yukai Huang
 *	NTUST 2014
 */
#include <iostream>
#include <iomanip>
#include <cmath>
#include <stdio.h>

using namespace std;

int gcd(int a, int b);
int* findCoprimeList(int i, int *z);
int mPowMod(int x, int n, int mod);

int* findCoprimeList(int n, int *z)
{
	int* temp = new int[n];
	for (int k = 0; k < n; k++) temp[k] = 0;
	int* coprimes;

	int size = 0;

	for (int j = 1; j < n; j++)
	{
		int k = gcd(j, n);
		if (k == 1)
		{
			temp[j] = 1;
			size++;
		}
	}

	coprimes = new int[size];

	int index = 0;
	for (int j = 1; j < n; j++)
	{		
		if (temp[j] == 1)
		{
			coprimes[index] = j;
			index++;
		}
	}
	*z = size;

	delete[] temp;
	return coprimes;
}

int gcd(int a, int b)
{
	int c;
	while ( a != 0 ) {
		c = a; a = b%a;  b = c;
	}
	return b;   
}

int mPowMod(int x, int n, int m)
{
	int remained = x;
	for (int i = 1; i < n; i++)
	{
		remained *= x;
		remained %= m;
	}
	return remained;
}

int main()
{
	/////////////////////2.b/////////////////////
	int count = 0;
	int size;
	int* coprimes = findCoprimeList(101, &size);
	bool flag = true;
	for (int j = 1; j < size; j++)
	{
		for (int k = 1; k < 100; k++){
			int remained = mPowMod(coprimes[j], k, 101);
			if (remained == 1)
			{
				flag = false;
				break;
			}
		}
		int remained = mPowMod(coprimes[j], 100, 101);
		
		if (remained && flag)
		{
			cout << setw(5) <<coprimes[j];
			count++;
		}		
		else
		{
			flag = true;
		}		
	}
	cout << endl << "total " << count << " primitive roots" << endl;
	/////////////////////////////////////////////

	/////////////////////2.c/////////////////////
	for (int i = 1; i <= 10; i++)
	{
		//2, 4, 5, 10, 20, 25, 50
		printf("%d ^ 2 = %d mod 101\n", i, mPowMod(i, 2, 101));
		printf("%d ^ 4 = %d mod 101\n", i, mPowMod(i, 4, 101));
		printf("%d ^ 5 = %d mod 101\n", i, mPowMod(i, 5, 101));
		printf("%d ^ 10 = %d mod 101\n", i, mPowMod(i, 10, 101));
		printf("%d ^ 20 = %d mod 101\n", i, mPowMod(i, 20, 101));
		printf("%d ^ 25 = %d mod 101\n", i, mPowMod(i, 25, 101));
		printf("%d ^ 50 = %d mod 101\n", i, mPowMod(i, 50, 101));
		printf("%d ^ 100 = %d mod 101\n", i, mPowMod(i, 100, 101));
		printf("\n\n");
	}
	////////////////////////////////////////////


	/////////////////////2.d/////////////////////
	int occurance[37] = {0};
	for (int i = 1; i <= 36; i++)
	{
		int remained =  mPowMod(i, 2, 37);
		occurance[remained]++;
		printf("%d ^ 2 = %d mod 37\n", i, remained);
	}
	for (int i = 1; i <= 36; i++) {cout << setw(3) << i;}
	cout << endl;
	for (int i = 1; i <= 36; i++) {cout << setw(3) <<occurance[i];}
	////////////////////////////////////////////

	return 0;
}