t_sptest.c

大数的计算包括加减乘除

/* t_spTest.c */

/******************* SHORT COPYRIGHT NOTICE*************************
This source code is part of the BigDigits multiple-precision
arithmetic library Version 1.0 originally written by David Ireland,
copyright (c) 2001 D.I. Management Services Pty Limited, all rights
reserved. It is provided "as is" with no warranties. You may use
this software under the terms of the full copyright notice
"bigdigitsCopyright.txt" that should have been included with
this library. To obtain a copy send an email to
<[e-mail]> or visit <www.di-mgt.com.au/crypto.html>.
This notice must be retained in any copy.
****************** END OF COPYRIGHT NOTICE*************************/

/*	The same procedures as for t_mpTest.c but using the
	single-digit functions (except add and subtract!).
	Note that the spMultiply and spDivide functions were
	designed as specialised sub-routines for their mp
	uncles.
*/

#include <stdio.h>
#include <assert.h>
#include "bigdigits.h"

DIGIT_T u;
DIGIT_T v;
DIGIT_T w;
DIGIT_T p[2];
DIGIT_T q;
DIGIT_T r;
DIGIT_T p1;
DIGIT_T p2;
DIGIT_T p3;
DIGIT_T g;

void ClearAll(void)
{
	u = 0;
	v = 0;
	w = 0;
	p[0] = 0;
	p[1] = 0;
	q = 0;
	r = 0;
	g = 0;
	p1 = 0;
	p2 = 0;
	p3 = 0;
}

DIGIT_T MakeSinglePrime(DIGIT_T maxsize)
{
	/*	WARNING: This is not cryptographically secure
		because the random number generator isn't
	*/
	DIGIT_T p;

	/* Pick a random number  */
	p = spPseudoRand(0, maxsize);

	/* Set lowest bit to make sure number is odd */
	p |= 0x1;

	/* Check if prime */
	while (!spIsPrime(p, 20))
	{
		/* Else keep adding 2 until prime */
		p += 2;
	}
	return p;
}

main()
{
	DIGIT_T m;

	/*	Force linker to include copyright notice in 
		executable object image */
	copyright_notice();
		
	ClearAll();

	/* ---- Multiply and divide ---- */
	printf("Multiply and divide:\n");
	/* Multiply two random numbers p = u * v */
	u = spPseudoRand(0, MAX_DIGIT);
	v = spPseudoRand(0, MAX_DIGIT) | HIBITMASK;
	/* Making sure that v is "normalised" */
	spMultiply(p, u, v);
	printf("u=%08lx\n", u);
	printf("v=%08lx\n", v);
	printf("p=u*v=%08lx %08lx\n", p[1], p[0]);

	/* q = p / v, r = p % v */
	spDivide(&q, &r, p, v);
	printf("q=p/v=%08lx <=Check q == u\n", q);
	printf("r=p mod v=%08lx <=Check r == 0\n", r);
	/* Check q == u and r == 0 */
	assert(q == u);
	assert(r == 0);

	ClearAll();

	printf("Multiply and divide worked OK\n");

	/* ---- Greatest Common Divisor ---- */
	printf("Greatest Common Divisor:\n");
	/* Pick 3x random half-size primes p1, p2, p3 */
	p1 = MakeSinglePrime(MAX_HALF_DIGIT);
	p2 = MakeSinglePrime(MAX_HALF_DIGIT);
	p3 = MakeSinglePrime(MAX_HALF_DIGIT);
	printf("p1=%08lx\n", p1);
	printf("p2=%08lx\n", p2);
	printf("p3=%08lx\n", p3);

	/* Calculate two products from these primes */
	u = p1 * p2;
	v = p1 * p3;
	printf("u=p1*p2=%08lx\n", u);
	printf("v=p1*p3=%08lx\n", v);

	/* Now calculate g = gcd(u, v) */
	g  = spGcd(u, v);
	/* And check that g == p1 */
	printf("gcd(u,v)=%08lx <=Check g == p1\n", g);
	assert(g == p1);
	printf("Greatest Common Divisor worked OK\n");

	/* ---- Modular Inverse ---- */
	printf("Modular Inverse:\n");
	/* Use previous prime as modulus, v */
	v = p1;
	/* and pick a small multiplier, m */
	m = spPseudoRand(1, MAX_HALF_DIGIT);

	/* Set u = (vm - 1) */
	u = v * m - 1;

	printf("u=%08lx\n", u);
	printf("v=%08lx\n", v);

	/* Calculate w = u^-1 mod v */
	spModInv(&w, u, v);
	printf("w = u^-1 mod v=%08lx <=Check w == v-1\n", w);

	/* Check that g = (w * u) mod v == 1 */
	spModMult(&g, w, u, v);
	printf("w * u mod v=%08lx <=Check == 1\n", g);
	assert(g == 1);
	printf("Modular inverse worked OK\n");

	/* For further checks do RSA calculation - see t_spRSA.c */

	return 0;
}