Investigating GCD In Euclidean Domains
Investigating GCD in Euclidean DomainsRohil Prasadunder mentorship of Tanya KhovanovaPRIMES 2013May 18, 2013
W HAT IS GCD?The greatest common divisor, or GCD, of two integers is thelargest integer that divides both of them.IMany algorithms use GCD calculation, one of the morefamous being the RSA encryption algorithm.ISeveral algorithms have been devised to efficientlycalculate GCD for integers.
T HE E UCLIDEAN A LGORITHM
T HE E UCLIDEAN A LGORITHM
T HE E UCLIDEAN A LGORITHM
T HE E UCLIDEAN A LGORITHM
T HE E UCLIDEAN A LGORITHM
T HE B INARY GCD A LGORITHM
T HE B INARY GCD A LGORITHM
T HE B INARY GCD A LGORITHM
T HE B INARY GCD A LGORITHM
T HE B INARY GCD A LGORITHM
T HE B INARY GCD A LGORITHM
T HE B INARY GCD A LGORITHM
T HE B INARY GCD A LGORITHM
T HE B INARY GCD A LGORITHM
E UCLIDEAN D OMAINSWe can extend our definition of GCD to arbitrary Euclideandomains.IA Euclidean domain E is a principal ideal domain with afunction f such that for any nonzero a and b in E, thereexists q and r in E with a bq r and f (r) f (b). Thisfunction is called a norm, and q is called the quotient of aand b.IThe integers are an example of a Euclidean domain withnorm f (a) a . We work in Z[ 2] and Z[ 3].I
F INDING GCD IN E UCLIDEAN D OMAINSWhat are some ways of efficiently calculating GCD inEuclidean domains?IOption 1: Calculate a quotient
F INDING GCD IN E UCLIDEAN D OMAINSWhat are some ways of efficiently calculating GCD inEuclidean domains?IOption 1: Calculate a quotientIOption 2: Divide out by a small prime
F INDING GCD IN E UCLIDEAN D OMAINSWhat are some ways of efficiently calculating GCD inEuclidean domains?IOption 1: Calculate a quotientIOption 2: Divide out by a small primeIOption 3: Approximate division
O PTION 1: C ALCULATING THE QUOTIENTI The quotient of elements in Z[ 2] is calculated as follows: a b 2c d 2 (a b 2)(c d 2)c2 2d2 ac 2bdc2 2d2 (bc ad) 2c2 2d2
O PTION 1: C ALCULATING THE QUOTIENTI The quotient of elements in Z[ 2] is calculated as follows: a b 2c d 2I (a b 2)(c d 2)c2 2d2 ac 2bdc2 2d2 (bc ad) 2c2 2d2Rounding each component to the nearest integer gives thequotient.
O PTION 1: C ALCULATING THE QUOTIENTI The quotient of elements in Z[ 2] is calculated as follows: a b 2c d 2II (a b 2)(c d 2)c2 2d2 ac 2bdc2 2d2 (bc ad) 2c2 2d2Rounding each component to the nearest integer gives thequotient. Quotient calculation is identical in Z[ 3].
O PTION 2: D IVISION BY A SMALL PRIMEIWe use primes of norm 2 because it is easiest to check fordivisibility.
O PTION 2: D IVISION BY A SMALL PRIMEIWe use primes of norm 2 because it is easiest to check fordivisibility.IPrimes with small components have the fastestimplemented division.
O PTION 2: D IVISION BY A SMALL PRIMEIWe use primes of norm 2 because it is easiest to check fordivisibility.IPrimes with small components have the fastestimplemented division. We use 1 3 for Z[ 3] and 2 2 for Z[ 2].I
O PTION 3: A PPROXIMATE DIVISIONICalcuation of the quotient limits the Euclidean algorithm’sruntime.
O PTION 3: A PPROXIMATE DIVISIONICalcuation of the quotient limits the Euclidean algorithm’sruntime.IA possible solution to this is to approximate the quotientquickly.
O PTION 3: A PPROXIMATE DIVISIONICalcuation of the quotient limits the Euclidean algorithm’sruntime.IA possible solution to this is to approximate the quotientquickly. Current implementations for Z[ 2] and Z[ 3] involvesbitshifting the components of each number by about halftheir bitsize and approximating the quotient with these.I
C OMPARING ALGORITHMS
F UTURE R ESEARCHThere are many directions in which this research can be taken: I Extend ideas to Z[ d] for squarefree d.
F UTURE R ESEARCHThere are many directions in which this research can be taken: I Extend ideas to Z[ d] for squarefree d.IImprove performance of the new ‘binary’ and‘approximate division’ algorithms.
F UTURE R ESEARCHThere are many directions in which this research can be taken: I Extend ideas to Z[ d] for squarefree d.IIImprove performance of the new ‘binary’ and‘approximate division’ algorithms. Find worst cases for the Euclidean algorithm in Z[ d].
A CKNOWLEDGMENTSI would like to acknowledge the following:IStefan Wehmeier and Ben Hinkle of Mathworks.IMy mentor Tanya Khovanova.IThe MIT PRIMES Program.IMy family.
EUCLIDEAN DOMAINS We can extend our definition of GCD to arbitrary Euclidean domains. I A Euclidean domain E is a principal ideal domain with a function f such that for any nonzero a and b in E, there exists q and r in E with a bq r and f(r) f(b).
Lone Star GCD Lower Trinity GCD I 11 Anderson County UWCD Neches & Trinity Valleys GCD Panola County GCD Pineywoods GCD Rusk County GCD 14 Lower Trinity GCD Southeast Texas GCD J 7 Kinney County GCD Real-Edwards C and R District 9 Bandera County River Authority & Ground Water District Headwaters GCD
Coastal Plains GCD Culberson County GCD Fayette County GCD Goliad County GCD Hickory UWCD No. 1 Lone Star GCD Middle Trinity GCD Neches & Trinity Valleys GCD North Plains GCD Panhandle GCD Pecan Valley GCD South Plains UWCD
Lone Star GCD - 1/6 2 0 49. L one W lf GCD - 2/ 0 5 0. Lo st Pine GCD - 1 / 2 5 1. Lowe rT in ty GCD - /7 2 06 52. McMullen GCD - 11/6/2001 53. Medi na Cou ty G D - 8 /26 19 5 4. Me nard Cou ty UWD - 8 /1 9 55. Mesa UWCD - 1/20/1990 . Mid-East Texas GCD Post Oak Savannah GCD
Euclidean Spaces: First, we will look at what is meant by the di erent Euclidean Spaces. { Euclidean 1-space 1: The set of all real numbers, i.e., the real line. For example, 1, 1 2, -2.45 are all elements of 1. { Euclidean 2-space 2: The collection of ordered pairs of real numbers, (x 1;x 2), is denoted 2. Euclidean 2-space is also called .
The groundwater resources are the Carrizo-WilcoxAquifer, the Queen City Aquifer, and the Sparta Aquifer. Carrizo-WilcoxAquifer Regional water planning areas-Subsurface 20 —V 12 4 5 21 11. I GCD Groundwater Conservation District UWCD Underground WaterConservation District Outcrop 1. Bee GCD 2. Bluebonnet GCD 3. BrazosValley GCD 4 .
Feb 05, 2010 · Euclidean Parallel Postulate. A geometry based on the Common Notions, the first four Postulates and the Euclidean Parallel Postulate will thus be called Euclidean (plane) geometry. In the next chapter Hyperbolic (plane) geometry will be developed substituting Alternative B for the Euclidean Parallel Postulate (see text following Axiom 1.2.2).
Traffic to ParkLogic Keep profitable domains Traffic monetized across parking, affiliate and direct advertising networks Via DNS template Owned registered domains Inbound Traffic Unpaid domains Expired domains Parked domains Domains can be split into unpaid, expired and parked domains by brand. Drop unprofitable domains DNS to ParkLogic
Text and illustrations 22 Walker Books Ltd. Trademarks Alex Rider Boy with Torch Logo 22 Stormbreaker Productions Ltd. MISSION 3: DESIGN YOUR OWN GADGET Circle a word from each column to make a name for your secret agent gadget, then write the name in the space below. A _ Draw your gadget here. Use the blueprints of Alex’s past gadgets on the next page for inspiration. Text and .
