|
|
|
SWRIMS HIGH SCHOOL WORKSHOPS
|
Factoring and Primality Testing
Wednesday, 15 April 1998, 7:00 PM - 9:00 PM Wednesday, 22 April 1998, 7:00 PM - 9:00 PM Wednesday, 29 April 1998, 7:00 PM - 9:00 PM
Mathematics Building, Room 101
|
(Note: This is one six-hour workshop split across three days.)
|
|
Workshop schedule:
|
If you have questions about this workshop, here are the people who
ran it:
WORKSHOP OUTLINE
Why is factoring of interest and how do we measure our ability to
factor? (Alexander Perlis)
- Interest is because security of many public-key cryptosystems (like
RSA) rests on the difficulty of factoring.
- Historically, people have wanted to factor many sequences of numbers;
two important examples are the Fermat numbers and the Mersenne numbers.
How far down the line we can factor these numbers is a measure of our current
factoring ability. Define Fermat and Mersenne numbers, write the first
few on the board.
- Also, companies like RSA and others issue "challenges", specific
numbers that are considered "just beyond grasp" of what can be
factored. These challenges get broken after a few years.
- Mention some articles from last twenty years of Math Comp.
Let's factor some numbers
Differences of two squares (Aaron)
- Writing 8999999 as 90000000-1 = 3000^2-1^2, we have a difference of
squares and quickly obtain the factorization 8999999 = (3000-1)(3000+1),
i.e., 2999*3001. This was much faster than trial division. Can we do the
same with 899999879? (Answer: yes)
- Was the difference of squares approach a fluke, or can we always factor
numbers this way? Have students to worksheet, goal is to see that there
is a one-to-one correspondence between factorizations N=A*B and writing
N as a difference of squares N=U^2-V^2, given by A=U-V, B=U+V, or in the
other direction, U = (A+B)/2 and V = (B-A)/2. (We adopt the convention
that all variables represent positive quantities, and when we write N=A*B,
we always take A <= B.)
Turning difference of squares into an algorithm (Aaron)
From N=A*B to N | A*B
- (Aaron) 1349 example
- (Alex) Adding MOD: The 857525321 example
- Challenge: do 1791072187 (takes 37 steps)
|
|
Workshop participants:
|
Canyon del Oro High School
Tucson, Arizona
Christopher Yetman's students:
Micah Bickford
Mark Major
Phil Hughes
Joseph Vega
Tucson High School
Tucson, Arizona
Ron Hopley's students:
Jesse Stone
Doniphan Pattison
David Obregon
|
Summary: 0 teachers and 7 students.
|
|
Webpage: http://www.math.arizona.edu/~rims/workshops/workshop15Apr98.html
Webmaster: Alexander Perlis
|
|