Question & Answer: 1) write any C++ or java programming for each one of these as follows:…..

1) write any C++ or java programming for each one of these as follows:

a) Is 7 a primitive root modulo 65537? How many calculations” multiplications” are needed?

Don't use plagiarized sources. Get Your Custom Essay on

GET AN ESSAY WRITTEN FOR YOU FROM AS LOW AS $13/PAGE

Order Essay

b) solve 7^x ≡ 2 (mod 65537)

c) A first non- trivial approach to solving discrete logarithms is the baby step giant algorithm of shanks. first learn it and use it to solve

2^x ≡ 18465502604450 (mod 247457076132467) but before using this method, try to solve this DLP by brute force. how did it go? Calculate how much storage space you need to implement the Shanks algorithm for this problem.

Expert Answer

a) Yes 7 is a primitive root modulo of 65537. We will be needing 65536 calculations to find this out.

#include <stdio.h>
#include <math.h>

int main()
{
long int m;
int a,n;
printf(“Enter the value of a : “);
scanf(“%d”,&a);
printf(“Enter the value of n : “);
scanf(“%d”,&n);
int r[n+1];
int i,f=0;
for(i=1;i<=n;i++)
{
r[1]=0;
}
for(i=1;i<n;i++)
{
m=pow(a,i);
m=m%n;
printf(“a = %d m = %d n = %d r = %dn”,a,i,n,m);

if (r[m]==1)
{
f=1;
break;
}
else
{
r[m]++;
}
}
if(f==1)
{
printf(“No”);
}
else
{
printf(“Yes”);
}
return 0;
}

	#include <NTL/ZZ.h>


	#define TABLE_SIZE 21677779

	#define T 724288
	#define B 524288

	int collisions = 0;

	NTL_CLIENT

	typedef struct hashlist
	{
	int value;
	hashlist *p_coll;
	hashlist *p_next;
	} HASHLIST;

	typedef struct hashtable
	{
	int size;
	// pointer to a pointer to a linked list
	HASHLIST **table;
	} HASHTABLE;

	HASHTABLE *htCreate( size_t size )
	{
	HASHTABLE *fresh_table;

	if( (fresh_table = (HASHTABLE*)malloc(sizeof(HASHTABLE))) == NULL )
	{
	return NULL;
	}

	if( (fresh_table->table = (HASHLIST*)malloc(sizeof(HASHLIST)*size)) == NULL )
	{
	return NULL;
	}

	int i;
	for( i = 0; i < size; i++ ) {
	fresh_table->table[i] = NULL;
	}

	fresh_table->size = size;

	return fresh_table;
	}

	int htHash( HASHTABLE *t, ZZ value )
	{
	unsigned long int result = 0;
	/*
	discrete logarithm results in pseudo random number
	so I can just apply the modulus table size
	*/
	result = to_int(MulMod(value, 1, to_ZZ(t->size)));

	return result;
	}

	HASHLIST *htNewExponent( int value )
	{
	HASHLIST *newList;

	if( (newList = (HASHLIST*)malloc(sizeof(HASHLIST))) == NULL )
	{
	return NULL;
	}

	if( ( newList->value = value ) == NULL ) {
	return NULL;
	}

	newList->p_coll = NULL;
	newList->p_next = NULL;

	return newList;
	}

	void htInsert( HASHTABLE *t, ZZ key, int value )
	{
	int index = 0;
	HASHLIST *newExponent;
	HASHLIST *next ;
	HASHLIST *prev;

	index = htHash(t, key);
	next = t->table[index];

	/* collision */
	if( next != NULL )
	{

	/* walk to the end */
	while( next->p_coll != NULL )
	{
	prev = next;
	next = next->p_coll;
	}

	newExponent = htNewExponent(value);
	next->p_coll = newExponent;

	collisions++;
	}
	else
	{
	newExponent = htNewExponent(value);

	/* start */
	if( next == t->table[ index ] )
	{
	newExponent->p_next = next;
	t->table[index] = newExponent;

	}
	/* end */
	else if ( next == NULL )
	{
	prev->p_next = newExponent;
	}
	/* walking */
	else
	{
	newExponent->p_next = next;
	prev->p_next = newExponent;
	}
	}
	}

	/*
	find our exponents
	*/
	int findExponents( HASHTABLE *t, ZZ key, int x0, ZZ g, ZZ h, ZZ p )
	{
	ZZ x;
	int index = 0;
	HASHLIST *pair;

	index = htHash(t, key);
	pair = t->table[index];


	if( pair == NULL ) {
	return NULL;
	}
	else
	{
	x = (to_ZZ(pair->value) * B) + to_ZZ(x0);

	if( PowerMod(g, x, p) == h )
	{
	//cout << PowerMod(g, x, p) << endl;
	printf(“%d * B + %d = xn”, pair->value, x0);
	return 1;
	}

	// walk collisions
	while( pair->p_coll != NULL )
	{
	x = (to_ZZ(pair->p_coll->value) * B) + to_ZZ(x0);

	if( PowerMod( g, x, p ) == h )
	{
	//cout << PowerMod(g, x, p) << endl;
	printf(“%d * B + %d = xn”, pair->p_coll->value, x0);
	return 1;
	}

	pair = pair->p_coll;
	}

	return pair->value;
	}
	}

	int main()
	{
	HASHTABLE *tabulka = htCreate( TABLE_SIZE );

	if( tabulka == NULL )
	{
	return -1;
	}

	/* time */
	double t;

	/*
	g = h^x mod p, find x!
	*/
	ZZ p = to_ZZ(“13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084171”);
	ZZ g = to_ZZ(“11717829880366207009516117596335367088558084999998952205599979459063929499736583746670572176471460312928594829675428279466566527115212748467589894601965568”);
	ZZ h = to_ZZ(“3239475104050450443565264378728065788649097520952449527834792452971981976143292558073856937958553180532878928001494706097394108577585732452307673444020333”);

	int tbl;
	ZZ x;
	ZZ hgx1;
	ZZ gpowB;
	ZZ gx1 = h;
	ZZ gx0 = to_ZZ(“1”);

	/*
	precompute g^-B, there is no need
	for computing it every iteration
	*/
	PowerMod( gpowB, g, B, p );
	InvMod( gpowB, gpowB, p );

	t = GetTime();

	/* ~17s */
	printf( “Building hashtable…nn” );

	int x1 = 1;
	for( ; x1 < T; x1++ )
	{
	/* compute x1g^-B /
	MulMod( gx1, gx1, gpowB, p );

	/* insert into table */
	htInsert( tabulka, gx1, x1 );
	}
	printf( “Collisions:%dn”, collisions);

	t = GetTime() – t;
	printf( “nTime: %f secn”, t );

	/* ~13s */
	printf( “Searching for collision…n” );

	int x0 = 1;
	for(; x0 < B; x0++)
	{
	/* (g^B)^x0 */
	MulMod(gx0, gx0, g, p);

	if(findExponents( tabulka, gx0, x0, g, h, p ) == 1)
	break;
	}

	t = GetTime() – t;

	printf( “nTime: %f secn”, t );

	getchar();
	return 0;
	}

Still stressed from student homework?

Get quality assistance from academic writers!

Order now