The University of Arizona / MATHEMATICS

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

  • Start by factoring the numbers written on the board. Ask students how they would do it. (Goal: trial division.) Let's automate it: together write pseudocode for trial division on the board.
    • INPUT N
      FOR I=1 TO SQRT(N)
          WHILE (N/I = INT(N/I))
              PRINT I
              N = N/I
              ENDWHILE
          NEXT I
      IF (I*I>N)
          PRINT I
          ENDIF

  • After that's clear, to save time, provide the pre-written TI82 program "TRIALDIV" and an example of using it.
  • Also put "8999999" and "899999879" on the board, have students factor those. (Latter won't trial divide in a reasonable amount of time.) Observe that trial division on TI calculators takes about 1 minute for 5000 trial divides.

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)

  • Since every factorization N=A*B corresponds to writing N as a difference of two squares, one should be able to search for factorizations N=A*B by instead searching for representations N=U^2-V^2.
  • Example search: factor 8810913061. (Takes 3 steps.)
  • (Alex) Write pseudocode for an algorithm. Observe that the algorithm must work (i.e., it will always eventually find the factor closest to the square root of N)
    • INPUT N
      T = INT(SQRT(N))+1
      S = SQRT(T*T - N)
      WHILE (S <> INT(S))
          T = T + 1
          S = SQRT(T*T - N)
          ENDWHILE
      PRINT T-S,T+S

  • Give out the prewritten TI program FERMATFC, example of using it. Let them play with the program for 5 minutes

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