Mathematics

From My Wiki
Jump to: navigation, search

modulus or modulo finds the remainder of a division.

19 mod 20 = 19

22 mod 20 = 2

39 mod 20 = 19

Google math puzzle

original

How to solve this:

  1. Generate decimal digits of e
  2. Find a prime number in consecutive digits.

Finding if a number is prime is easy. See if the number can be divided by any number between 2 and its square root, if it can it is prime.

Large quantity of decimal digits of e can be found here: [1] but wouldn't it be more fun to generate them ourselves? This is where a spigot algorithm comes into play.

The basic idea behind a spigot algorithm for an irrational number is that you can find the nth decimal digit of the number in some base without having to calculate any of the digits to the left of it. That sounds like an impossible trick, but it's based on the fact that some irrational numbers can be expressed as infinite summations, where each piece of the summation contributes to only one digit of the number (again, in some base). source

e (also known as the natural logarithm) is approx. 2.718281828.

Lets do this! See: http://alaning.me:8080/root/primeine

RSA (public key cryptography)

RSA is an algorithm that implements public key cryptography. Public key cryptography can be referred to as asymmetric key cryptography because two different keys involved in the encryption of information. There is a private key and a public key and they work in a way such that if a message is encrypted with a public key it can only be decrypted by the private key, and vice versa. This allows a user to freely distribute his public keys to anyone because a message encrypted with the public key can not be decrypted by it. Imagine an open box. Anyone can put things inside it and then close it shut. Once closed it can no longer be opened except by the person holding the right key.

The mathematical box in public key crypto is created by the multiplication of large primes. Large primes are used because its hard* to factor the result to get back the original primes. This keeps the keys secure because you can't derive one from the other. See also Integer factorization

  • Hard as in there currently exists no polynomial time algorithm to solve this problem. Polynomial time is O(n^k) for some constant k. A polynomial time algorithm runs in a time proportional only to the key length raised to some constant power. These are "easy" or "tractable", "feasible", "efficient", or "fast" problems.

"Hard," or exponential time problems run in operational time that increases proportional to some number raised to the power of the length of the key ("exponential time"). O(k^n) for some constant k.

Imagine an input that increased in size slightly, a polynomial time will solve it with a slight increase in processing time compared to original input but an exponential time algorithm will take significantly much longer to solve it compared to the original input.

Edit: this is actually related to "Big O" notation...

"Computers don't do well with arbitrarily large numbers. We can make sure that the numbers we are dealing with do not get too large by choosing a maximum number and only dealing with numbers less than the maximum. We can treat the numbers like the numbers on an analog clock. Any calculation that results in a number larger than the maximum gets wrapped around to a number in the valid range.

In RSA, this maximum value (call it max) is obtained by multiplying two random prime numbers. The public and private keys are two specially chosen numbers that are greater than zero and less than the maximum value (call them pub and priv). To encrypt a number, you multiply it by itself pub times, making sure to wrap around when you hit the maximum. To decrypt a message, you multiply it by itself priv times, and you get back to the original number. It sounds surprising, but it actually works. This property was a big breakthrough when it was discovered. "-http://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/


A working example

/*
Proof of concept. Does not work with large (>1000) numbers. Should rewrite in python to deal with that. I suck at C data types. 

Go through using these numbers: https://en.wikipedia.org/wiki/RSA_(algorithm)#A_working_example

Use the following:
p= 61
q=53
e=17
m=65

Data types
http://msdn.microsoft.com/en-us/library/vstudio/s3f49ktz.aspx
*/

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <sstream>

void factor(int a);
void coprimes(int a);
int mul_inv(int a, int b);
int modular(int base, unsigned int exp, unsigned int mod);

int main()
{
	
	std::string mystr;
	int p=0, q=0;
	std::cout << "Choose two distinct prime numbers p, q" << std::endl; 
	std::cout << "p: ";
	getline(std::cin, mystr);
	std::stringstream(mystr) >> p;
	std::cout << "q: ";
	getline(std::cin, mystr);
	std::stringstream(mystr) >> q;

	int n = p * q;
	int toilet = (p - 1) * (q - 1);

	printf("n = p * q: %d\n",n);
	printf("toilet = (p - 1) * (q - 1): %d\n", toilet);
	printf("\n");
	
	printf("coprimes of %d: ", toilet);
	coprimes(toilet);
	printf("\n");
	printf("Pick a coprime: ");
	
	int e = 0;
	getline(std::cin, mystr);
	std::stringstream(mystr) >> e;
	printf("\n");
	int d = 0; //multiplicative inverse of e (mod(toilet))
	d = mul_inv(e, toilet);

	std::cout << "d: (modular multiplicative inverse): " << d << std::endl;
	//std::cout << mul_inv(3, 11) << std::endl;
	printf("\n");
	std::cout << "Keys are generated. " << std::endl;
	printf("public key is (n = %d, e = %d)\n", n, e);
	printf("private key is (n = %d, d = %d)\n", n, d);
	printf("\n");
	
	printf("Encryption function: c(m) = pow(m,%d) (mod %d)\n",e,n);
	printf("Decryption function: m(c) = pow(c,%d) (mod %d)\n", d, n);
	printf("\n");
	int m = 0;
	printf("Plaintext message to encrypt: m=");
	getline(std::cin, mystr);
	std::stringstream(mystr) >> m;

	printf("Encrypting...\n", e, n);
	int c = modular(m, e, n);
	printf("Encrypted cyphertext ");
	printf("using public key (n = %d, e = %d)\n", n, e);
	printf("c=%d\n",c);

	printf("Cyphertext to decrypt: c=");
	getline(std::cin, mystr);
	std::stringstream(mystr) >> c;
	printf("Decrypting...\n", d, n);
	m = modular(c, d, n);
	printf("Decrypted plaintext message ");
	printf("using private key (n = %d, d = %d)\n", n, d);
	printf("m=%d\n", m);

	getchar();
}

void factor(int a)
{
	int t = 0;
	for (t = 2; t < sqrt(a); t++)
	{
		if (a%t == 0){
			printf("%d, %d", t, a/t);
			break;
		}
	}
	
}

void coprimes(int a)
{
	int t = 2;
	for (t = 2; t < sqrt(a); t++)
	{
		if (a%t != 0){
			printf("%d ", t);
		}
	}
}

int mul_inv(int a, int b)
{
	//https://en.wikipedia.org/wiki/Modular_multiplicative_inverse
	int toilet = b;
	int t;
	int q;
	int x0 = 0;
	int x1 = 1;

	if (b == 1) 
	{ 
		return 1; 
	}
	while (a > 1) 
	{
		
		q = a / b;
		t = b;
		printf("Dividing %d by %d, got quotient of %d and remainder of %d\n", a, b, q, a%b);
		b = a % b;
		
		a = t;
		t = x0;
		printf("Updating x0:%d = %d - %d * %d \n", x1 - q * x0, x1, q, x0);
		x0 = x1 - q * x0;
		printf("Updating x1:%d\n", x1);
		x1 = t;
		
	}
	printf("latest x1:%d\n", x1);
	printf("adding this until positive:%d\n", toilet);
	if (x1 < 0) 
	{
		x1 += toilet;
	}
	printf("final x1:%d\n", x1);
	return x1;
}

int modular(int base, unsigned int exp, unsigned int mod)
{
	//https://en.wikipedia.org/wiki/Modular_exponentiation#Memory-efficient_method
	printf("Modular exponentiation: \nbase: %d exp: %d mod: %d\n", base, exp, mod);
	int c = 1;
	int e_prime = 1;
	for (e_prime = 1; e_prime <= exp; e_prime++)
	{
		printf("%d = (%d*%d) mod %d\n", (c*base) % mod, c, base, mod);
		c = (c*base) % mod;
		
	}
	return c;
}

should try rewrite in python because I'm not too sure how to handle large numbers .

Pi

The number π is a mathematical constant that is the ratio of a circle's circumference to its diameter, and is approximately equal to 3.14159.

But because we have computers we can get a more accurate representation using another spigot algorithm.

Pi is an important number that shows up not just in geometry and trigonometry because of its relation to circles, but also shows up in statistics, fractals, thermodynamics, mechanics, cosmology, number theory, and electromagnetism.

//http://www.mathpropress.com/stan/bibliography/spigot.pdf
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <queue>          // std::queue

int main(){
	
	const int N = 2000; //set how many digits to have. 

	const int arraysize = floor((10 * N) / 3);	
	int* A = new int[arraysize];
	int i,j;
	std::queue<int> predigits; 

	for(j=0;j<arraysize;j++)
	{
		A[j] = 2;
	}

	int quotient = 0;
	int remainder = 0;
	int final = 0;

	for(i=0;i<=N;i++){
		for(j=arraysize;j>=0;j--)
		{
			int denominator = 2 * j + 1;
			if (denominator == 1)
			{
				denominator = 10;
			}

			A[j] = 10 * A[j];
			A[j] = A[j] + quotient;
			quotient = A[j] / denominator;
			remainder = A[j] % denominator;
			quotient = quotient * j;
			final = A[j];
			A[j] = remainder;
		}
		
		final = final / 10;
		if(final==9)
		{
			//add
			predigits.push(final);
		}
		else if (final==10)
		{
			//set current to 0
			//increase others by 1 (9 becomes 0)
			//release others
			//hold current
			while(!predigits.empty())
			{
				int q = predigits.front();
				q = q + 1;
				
				if(q==10){
					q=0;
				}
				printf("%d",q);
				predigits.pop();
			}
			predigits.push(0);
		}
		else
		{
			//release others
			while(!predigits.empty())
			{
				printf("%d",predigits.front());
				predigits.pop();
			}
			//hold current
			predigits.push(final);
		}

		quotient=0;
		remainder=0;
	}
	printf("\n");
}