Welcome! The Trek BBS is the number one place to chat about Star Trek with likeminded fans. Please login to see our full range of forums as well as the ability to send and receive private messages, track your favourite topics and of course join in the discussions. If you are a new visitor, join us for free. If you are an existing member please login below. Note: for members who joined under our old messageboard system, please login with your display name not your login name. 

Science and Technology "Somewhere, something incredible is waiting to be known."  Carl Sagan. 

Thread Tools 
February 20 2014, 04:34 AM  #1 
Knives Out, 24/7/365

Number Theory
Is anyone here wellversed in number theory? Specifically, anything to do with modulus arithmetic, generators, and discrete functions. I have some questions. I guess this thread can be a general number theory thread, too. 
February 20 2014, 04:48 AM  #2 
Admiral
Location: North America

Re: Number Theory
__________________
“A life is like a garden. Perfect moments can be had, but not preserved, except in memory. LLAP” — Leonard Nimoy (19312015) 
February 20 2014, 04:51 AM  #3 
Knives Out, 24/7/365

Re: Number Theory
For instance, supposing I want all invertible elements in Z* of 35, how do I get that? I thought it was all primes that are not factors of 35, but apparently that's wrong. (For the sake of clarity: by "invertible" I am referring to multiplicative inversion.) 
February 20 2014, 04:52 AM  #4 
Admiral
Location: Kentucky

Re: Number Theory

February 20 2014, 04:56 AM  #5 
Admiral
Location: Kentucky

Re: Number Theory

February 20 2014, 05:04 AM  #6 
Admiral
Location: North America

Re: Number Theory
Are you simply discussing the set of integers modulo 35? See for example: http://www.math.niu.edu/~beachy/abst..._guide/14.html http://en.wikipedia.org/wiki/Finite_field#Examples http://en.wikipedia.org/wiki/Finite_ring Once we agree on notation, I can help you with this. I'll be in and out tonight and tomorrow, but I'll be here when I can.
__________________
“A life is like a garden. Perfect moments can be had, but not preserved, except in memory. LLAP” — Leonard Nimoy (19312015) 
February 20 2014, 05:08 AM  #7  
Knives Out, 24/7/365

Re: Number Theory


February 20 2014, 05:24 AM  #8 
Admiral
Location: North America

Re: Number Theory
A few questions, though. I assume 35 is just an example right? You want a general algorithm? If so, does it need to be efficient or theoretically of maximal efficiency, does efficiency matter at all, or is this just a oneshot deal, or something that you will do only a few times? A followup question is that if you must solve this problem over and over, will the modulus (e.g., 35) be small, or could it assume *any* value.
__________________
“A life is like a garden. Perfect moments can be had, but not preserved, except in memory. LLAP” — Leonard Nimoy (19312015) 
February 20 2014, 05:27 AM  #9 
Knives Out, 24/7/365

Re: Number Theory
I appreciate you being willing to help. 
February 20 2014, 05:30 AM  #10 
Admiral
Location: North America

Re: Number Theory
__________________
“A life is like a garden. Perfect moments can be had, but not preserved, except in memory. LLAP” — Leonard Nimoy (19312015) 
February 20 2014, 09:17 AM  #11 
Admiral
Location: Gov Kodos Regretably far from Boston

Re: Number Theory
__________________
We are quicksilver, a fleeting shadow, a distant sound... our home has no boundaries beyond which we cannot pass. We live in music, in a flash of color... we live on the wind and in the sparkle of a star! Endora, Bewitched 
February 20 2014, 01:31 PM  #12 
Admiral
Location: North America

Re: Number Theory
Notation/definitions:  Integer x is a divisor of integer y if and only if there is an integer q such that x*q=y.  A prime number is an integer greater than 1 whose only positive divisors are 1 and itself.  Integers x and y are coprime if and only if there is no prime number that is a divisor of both x and y (i.e., gcd(x,y)=1).  phi is Euler's totient function.  n is some integer such that n>=2.  Z_n is the ring of integers modulo n.  y is an inverse of x in Z_n if and only if (x*y)mod(n)=1. Lemma: If nonzero element x of Z_n is invertible (i.e., it has an inverse) then the inverse is unique. proof: If xy=xz=1 (under ring multiplication), then (y)(xy)=(y)(xz)=(y)(1), (yx)y=(yx)z=y, and y=z=y. QED. Theorem: Nonzero element x of Z_n is invertible if and only if x and n are coprime. proof: 1) Assume that x and n are coprime. Then, by Euler's totient theorem, (x*y)mod(n)=1 where y=x^(phi(n)1), so (y)mod(n) is the unique inverse of x. 2) Assume that x and n are not coprime. Then, there is a prime number p that is a prime factor of both x and n, so that x=p*w and n=p*m for some positive integers w and m. Assume (to the contrary) that y is an inverse of x. Then, there is an integer z such that x*y=z*n+1. Therefore, p*w*y=z*p*m+1, p*(w*yz*m)=1, and p is a divisor of 1, which is a contradiction. QED. Corollary: The number of invertible elements of Z_n equals phi(n). proof: Zero is never invertible and nonzero x are invertible if and only if x and n are coprime. QED. Special cases: a) 1 and n1 are invertible as themselves in Z_n. b) If the inverse of x is y, then the inverse of y is x. c) If n=p where p is prime, then Z_p is a field, which means that every nonzero element of Z_p is invertible. CC Code: Code:
////////////////////////////////////// ////////////////////////////////////// /* Language = c++ ansi std=c++98 fnononansibuiltins Werror Woldstylecast pedantic Wall W Wfloatequal Wpointerarith Wcastqual Wcastalign Wwritestrings Wconversion Wsigncompare Author = John  CorporalCaptain @ TrekBBS Date = February 20, 2014 Specification = "OK." means no bugs detected. Configure min_n and max_n for limits. Configure do_display switches for miscellaneous info. Configure do_check switches to perform checks or disable for speed. */ ////////////////////////////////////// // switches: unsigned int min_n = 2; // >= 2 unsigned int max_n = 20; // <= square root of UINT_MAX+1 bool do_display_totient = true; bool do_check_inverses = true; bool do_check_non_inverses = true; ////////////////////////////////////// #include <iostream> ////////////////////////////////////// unsigned int gcd (unsigned int a, unsigned int b) { // See http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations while (b != 0) { unsigned int t = b; b = a % b; a = t; } return a; } unsigned int totient (unsigned int x) { // See http://en.wikipedia.org/wiki/Euler's_totient_function unsigned int t = 0; for (unsigned int j=1; j<=x; j++) if (gcd(j,x) == 1) t++; return t; } unsigned int my_exp (unsigned int x, unsigned int y, unsigned int n /* >=2 */) { // (x^y) mod n, by successive squaring unsigned int x_to_2_to_j = x; // j=0 unsigned int a = 1; while (y != 0) { if ((y & 1) == 1) a = (a * x_to_2_to_j /* overflow possible here for large n */) % n; x_to_2_to_j = (x_to_2_to_j * x_to_2_to_j /* overflow possible here for large n */) % n; y = y >> 1; // j++ } return a; } ////////////////////////////////////// int main (int argc, char * argv []) { (void) argc; (void) argv; try { for (unsigned int n=min_n; n<=max_n; n++) { std::cout << std::endl; std::cout << "n = " << n << std::endl; const unsigned int totient_n = totient (n); if (do_display_totient) std::cout << "totient = " << totient_n << std::endl; unsigned int num_invs = 0; for (unsigned int x=0; x<n; x++) { //////// std::cout << "x = " << x << " 1/x = "; bool has_inverse = (gcd(x,n) == 1); if (has_inverse) { num_invs++; unsigned int inv_x = my_exp (x, totient_n1, n); std::cout << inv_x; if (do_check_inverses) { if (1 != ((x*inv_x)%n)) throw "Bug detected in calculation of inverse"; } } else { std::cout << ""; if (do_check_non_inverses) { for (unsigned int y=0; y<n; y++) if (1 == ((x*y)%n)) throw "Bug detected in determination of inverse nonexistence"; } } //////// std::cout << std::endl; } if (totient_n != num_invs) throw "Bug detected in calculation of number of inverses"; } std::cout << std::endl; std::cout << "OK." << std::endl; } catch (const char * message) { std::cerr << "Exception: " << message << "." << std::endl; } catch (...) { std::cerr << "Unknown exception." << std::endl; } return 0; } ////////////////////////////////////// ////////////////////////////////////// Output: Code:
n = 2 totient = 1 x = 0 1/x =  x = 1 1/x = 1 n = 3 totient = 2 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 2 n = 4 totient = 2 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x =  x = 3 1/x = 3 n = 5 totient = 4 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 3 x = 3 1/x = 2 x = 4 1/x = 4 n = 6 totient = 2 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x =  x = 3 1/x =  x = 4 1/x =  x = 5 1/x = 5 n = 7 totient = 6 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 4 x = 3 1/x = 5 x = 4 1/x = 2 x = 5 1/x = 3 x = 6 1/x = 6 n = 8 totient = 4 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x =  x = 3 1/x = 3 x = 4 1/x =  x = 5 1/x = 5 x = 6 1/x =  x = 7 1/x = 7 n = 9 totient = 6 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 5 x = 3 1/x =  x = 4 1/x = 7 x = 5 1/x = 2 x = 6 1/x =  x = 7 1/x = 4 x = 8 1/x = 8 n = 10 totient = 4 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x =  x = 3 1/x = 7 x = 4 1/x =  x = 5 1/x =  x = 6 1/x =  x = 7 1/x = 3 x = 8 1/x =  x = 9 1/x = 9 n = 11 totient = 10 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 6 x = 3 1/x = 4 x = 4 1/x = 3 x = 5 1/x = 9 x = 6 1/x = 2 x = 7 1/x = 8 x = 8 1/x = 7 x = 9 1/x = 5 x = 10 1/x = 10 n = 12 totient = 4 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x =  x = 3 1/x =  x = 4 1/x =  x = 5 1/x = 5 x = 6 1/x =  x = 7 1/x = 7 x = 8 1/x =  x = 9 1/x =  x = 10 1/x =  x = 11 1/x = 11 n = 13 totient = 12 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 7 x = 3 1/x = 9 x = 4 1/x = 10 x = 5 1/x = 8 x = 6 1/x = 11 x = 7 1/x = 2 x = 8 1/x = 5 x = 9 1/x = 3 x = 10 1/x = 4 x = 11 1/x = 6 x = 12 1/x = 12 n = 14 totient = 6 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x =  x = 3 1/x = 5 x = 4 1/x =  x = 5 1/x = 3 x = 6 1/x =  x = 7 1/x =  x = 8 1/x =  x = 9 1/x = 11 x = 10 1/x =  x = 11 1/x = 9 x = 12 1/x =  x = 13 1/x = 13 n = 15 totient = 8 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 8 x = 3 1/x =  x = 4 1/x = 4 x = 5 1/x =  x = 6 1/x =  x = 7 1/x = 13 x = 8 1/x = 2 x = 9 1/x =  x = 10 1/x =  x = 11 1/x = 11 x = 12 1/x =  x = 13 1/x = 7 x = 14 1/x = 14 n = 16 totient = 8 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x =  x = 3 1/x = 11 x = 4 1/x =  x = 5 1/x = 13 x = 6 1/x =  x = 7 1/x = 7 x = 8 1/x =  x = 9 1/x = 9 x = 10 1/x =  x = 11 1/x = 3 x = 12 1/x =  x = 13 1/x = 5 x = 14 1/x =  x = 15 1/x = 15 n = 17 totient = 16 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 9 x = 3 1/x = 6 x = 4 1/x = 13 x = 5 1/x = 7 x = 6 1/x = 3 x = 7 1/x = 5 x = 8 1/x = 15 x = 9 1/x = 2 x = 10 1/x = 12 x = 11 1/x = 14 x = 12 1/x = 10 x = 13 1/x = 4 x = 14 1/x = 11 x = 15 1/x = 8 x = 16 1/x = 16 n = 18 totient = 6 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x =  x = 3 1/x =  x = 4 1/x =  x = 5 1/x = 11 x = 6 1/x =  x = 7 1/x = 13 x = 8 1/x =  x = 9 1/x =  x = 10 1/x =  x = 11 1/x = 5 x = 12 1/x =  x = 13 1/x = 7 x = 14 1/x =  x = 15 1/x =  x = 16 1/x =  x = 17 1/x = 17 n = 19 totient = 18 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 10 x = 3 1/x = 13 x = 4 1/x = 5 x = 5 1/x = 4 x = 6 1/x = 16 x = 7 1/x = 11 x = 8 1/x = 12 x = 9 1/x = 17 x = 10 1/x = 2 x = 11 1/x = 7 x = 12 1/x = 8 x = 13 1/x = 3 x = 14 1/x = 15 x = 15 1/x = 14 x = 16 1/x = 6 x = 17 1/x = 9 x = 18 1/x = 18 n = 20 totient = 8 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x =  x = 3 1/x = 7 x = 4 1/x =  x = 5 1/x =  x = 6 1/x =  x = 7 1/x = 3 x = 8 1/x =  x = 9 1/x = 9 x = 10 1/x =  x = 11 1/x = 11 x = 12 1/x =  x = 13 1/x = 17 x = 14 1/x =  x = 15 1/x =  x = 16 1/x =  x = 17 1/x = 13 x = 18 1/x =  x = 19 1/x = 19 OK. Tested for: Code:
unsigned int min_n = 2; unsigned int max_n = 2000; bool do_display_totient = true; bool do_check_inverses = true; bool do_check_non_inverses = true;
__________________
“A life is like a garden. Perfect moments can be had, but not preserved, except in memory. LLAP” — Leonard Nimoy (19312015) 
February 20 2014, 01:43 PM  #13 
Admiral
Location: North America

Re: Number Theory
Code:
n = 35 totient = 24 x = 0 1/x =  x = 1 1/x = 1 x = 2 1/x = 18 x = 3 1/x = 12 x = 4 1/x = 9 x = 5 1/x =  x = 6 1/x = 6 x = 7 1/x =  x = 8 1/x = 22 x = 9 1/x = 4 x = 10 1/x =  x = 11 1/x = 16 x = 12 1/x = 3 x = 13 1/x = 27 x = 14 1/x =  x = 15 1/x =  x = 16 1/x = 11 x = 17 1/x = 33 x = 18 1/x = 2 x = 19 1/x = 24 x = 20 1/x =  x = 21 1/x =  x = 22 1/x = 8 x = 23 1/x = 32 x = 24 1/x = 19 x = 25 1/x =  x = 26 1/x = 31 x = 27 1/x = 13 x = 28 1/x =  x = 29 1/x = 29 x = 30 1/x =  x = 31 1/x = 26 x = 32 1/x = 23 x = 33 1/x = 17 x = 34 1/x = 34 OK.
__________________
“A life is like a garden. Perfect moments can be had, but not preserved, except in memory. LLAP” — Leonard Nimoy (19312015) 
February 20 2014, 03:34 PM  #14 
Knives Out, 24/7/365

Re: Number Theory
(1 != ((x*inv_x)%n)) So if a number times its inverse modulo n doesn't equal 1, it's not a valid inverse. Interesting that it takes more work to calculate the inverse than to check it, but then I think that's the whole point: an inverse can be verified in linear time but requires polynomial time to calculate. At least I'm starting to get why this is useful for cryptography. I appreciate you going to this trouble for me. I'll try to port the code to Python to see that I have a good understanding of it. It's a big help! 
February 20 2014, 06:52 PM  #15 
Admiral
Location: North America

Re: Number Theory
http://mathworld.wolfram.com/Success...areMethod.html http://en.wikipedia.org/wiki/Exponentiation_by_squaring I did it off the top of my head, so it's a little cryptic, maybe. As indicated, and maybe this will help my_exp(x,y,n)==my_exp2(x,y,n),where Code:
unsigned int my_exp2 (unsigned int x, unsigned int y, unsigned int n /* >=2 */) { // (x^y) mod n, by brute force unsigned int a = 1; for (unsigned int k=1; k<=y; k++) a = (a * x) % n; return a; } Note that the condition to avoid overflow is given on the line declaring max_n. Although undocumented, the condition is the same in my_exp2 and is for the same reason (can you see why?). Oh, beware of my omission of braces in some conditionals and loopcontrol statements (e.g., as in my_exp2)!
__________________
“A life is like a garden. Perfect moments can be had, but not preserved, except in memory. LLAP” — Leonard Nimoy (19312015) 
Bookmarks 
«
Previous Thread

Next Thread
»
Thread Tools  


All times are GMT +1. The time now is 09:09 AM.
Powered by vBulletin® Version 3.8.6
Copyright ©2000  2015, Jelsoft Enterprises Ltd.
FireFox 2+ or Internet Explorer 7+ highly recommended.
Copyright ©2000  2015, Jelsoft Enterprises Ltd.
FireFox 2+ or Internet Explorer 7+ highly recommended.