# Engaging students: Finding prime factorizations

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Brittnee Lein. Her topic, from Pre-Algebra: finding prime factorizations.

• How has this topic appeared in the news?

Prime factorization is key to protecting many aspects of modern convenience. The Fundamental Theorem of Arithmetic states that every number can be broken down into a sum of two prime numbers. For relatively small numbers, this is no big deal; but for very large numbers, not even computers can easily break these down. Many online security systems rely on this principle. For example, if you shop online and enter your credit card information, websites protect that information from hackers through a process of encryption.

Something for students to think about in the classroom: Can you come up with any formula to break down numbers into their prime factors?

Answer: No! That’s why encryption is considered a secure form of cryptography. To this date, there is no confirmed algorithm for prime factorization.

Prime factorization is a classic example of a problem in the NP class. An NP class problem can be thought of as a problem whose solution is easily verified once it is found but not necessarily easily or quickly solved by either humans or computers. The P vs. NP problem is one that has perplexed computer scientists and mathematicians since it was first formulated in 1971. Most recently, a German scientist Norbert Blum has claimed to solve the P vs. NP problem in this article: https://motherboard.vice.com/en_us/article/evvp34/p-vs-np-alleged-solution-nortbert-blum

Also in recent years, A Texas student has been featured on Dallas County Community Colleges Blog for his work to find an algorithm for prime numbers: http://blog.dcccd.edu/2015/07/%E2%80%8Btexas-math-student-strives-to-solve-the-unsolvable/

• How could you as a teacher create an activity or project that involves your topic?

An activity for inquiry based learning of prime numbers and prime factorization utilizes pop cubes. Students will start out with a single color-coded cube representative of the number two (the first prime), they will then move up the list of natural numbers with each prime number having its own color of cube. The composite numbers will have the same colors as their prime factors. The idea is that students will visually see that prime numbers are only divisible by themselves (each being a lone cube) and that composite numbers are simply composed of primes (multiple cubes). A good point of discussion is the meaning of the word “composite’. You could ask students what they think the word ‘composite’ means and what word it reminds them of. This leads into the idea that every composite number is composed of prime numbers. This idea comes from online vlogger Thom Gibson and the RL Moore Inquiry Based Learning Conference. Below is a picture demonstrating the cube idea:

This foundational idea can be segued into The Fundamental Theorem of Arithmetic and then into prime factorization.
One of the most practical real-world applications of prime factorization is encryption. This activity I found makes use of prime factorization in a way that is interesting and different from simply making factor trees. This worksheet would be a good assessment and challenge for students and mimics a real –world application.

https://www.tes.com/teaching-resource/prime-factors-cryptography-6145275

• How does this topic extend what your students should have learned in previous courses?

Though not actually ‘reducing’ the value of a number, prime factorization is the equivalency of numbers broken down into their smallest parts and then multiplied together. The idea of reducing numbers goes all the way back to elementary school when students are learning about fractions. Subconsciously they use a similar process to prime factorization when reducing fractions to simplest form. When reducing fractions to simplest form, the numerators and denominators themselves may not both necessarily be prime, but when put into simplest form, they are relatively prime. Being able to pick out factors of numbers –another relatively early grade school concept (going back to multiplication and division) — plays a huge deal in both fractions and prime factorization.

# Full lesson plan: Modular multiplication and encryption

Over the summer, I occasionally teach a small summer math class for my daughter and her friends around my dining room table. Mostly to preserve the memory for future years… and to provide a resource to my friends who wonder what their children are learning… I’ll write up the best of these lesson plans in full detail.

In this lesson, the students practiced their skills with multiplication and division to create modular multiplication tables. Though this is a concept ordinarily first encountered in an undergraduate class in number theory or abstract algebra, there’s absolutely no reason why elementary students who’ve mastered multiplication can’t do this exercise. This exercise strengthens the notion of dividing with a remainder and leads to a fun application with encrypting and decrypting secret messages. Indeed, this activity made be viewed as a child-appropriate version of the RSA encryption algorithm that’s used every time we use our credit cards. This was mentioned in two past posts: https://meangreenmath.com/2013/10/17/engaging-students-finding-prime-factorizations and https://meangreenmath.com/2013/07/11/cryptography-as-a-teaching-tool

This lesson plan is written in a 5E format — engage, explore, explain, elaborate, evaluate — which promotes inquiry-based learning and fosters student engagement.

Lesson Plan: Kid RSA Lesson

Other Documents:

Vocabulary Sheet

Three Letter Words

RSA Numbers

Modular Multiplication Assessment

Modular Multiplcation Practice

Kid RSA

# Engaging students: Finding prime factorizations

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Roderick Motes. His topic, from Pre-Algebra: finding prime factorizations.

A) How could you as a teacher create an activity or project that involves your topic?

“The magic words are squeamish ossifage”

-Plaintext decode of the RSA-196 challenge in the 1994 issue of Scientific American

Prime factorizations are an interesting topic. Being that prime factorization was a part of number theory which was, for several hundred years, considered the “last bastion of pure mathematics” we can often find it a struggle to relate the problem to students. But prime factorizations have found a use very recently.

In 1977 a paper was published submitting a possible encryption algorithm for computers that takes two very large prime numbers, multiplies them, and uses this to generate a key-value pair to make your information more secure. This encryption algorithm is currently the backbone of internet data exchange.

For students you can craft an activity around this ideas, framing them as being secret agents trying to hide data, that uses a naïve version of the RSA algorithm in order to generate keys. Even if you didn’t want the RSA algorithm you could use the idea of multiplying primes to generate some kind of cipher scheme which is not complex, and then use that. Students could be put into groups for the project and given a message which is encoded, and then they need to try and break it.

Clearly it would be untenable to give the students exceedingly large numbers but as a consequence of the fundamental theorem of arithmetic you can use smaller primes and still have unique cipher keys (2*5 is a perfectly valid key in RSA, as is 5*7, you can extend things to be 2*3*2 even.) You don’t have to use RSA cryptography, but it’s a good talking point. This could be an excellent project I think, but you as a teacher would need to take much time carefully building up everything to make sure students can do it.

B) How can this topic be used in your student’s future math and science courses?

This is a pretty difficult question for anything involving number theory but prime factorizations, as discussed above, are of particular interest to students who plan to take computer science. Understanding how things become cryptographically secure and implementation of the RSA algorithm and various cracking algorithms would not be out of place in an upper level high school comp. sci. course.

C) What interesting things can you say about the people who contributed to the discovery and/or development of this topic over time?

Number theory is hugely important to the history of mathematics as one of the oldest and most accessible areas of mathematical study. To look into the history of number theory is to look into the history of math itself. Prime factorization is an interesting part of number theory because primes are an interesting part of number theory.

In 300 BCE Euclid wrote Elements, largely considered to be one of in not the most important math book ever published. In Elements Euclid compiled what he knew to be the modern understanding of geometry, but he went a bit further as well. He discusses at length and eventually gives formal proof of, the fundamental theorem of arithmetic. The whole basis of the fundamental theorem is that numbers are either prime or composite, and if a number is composite we can break it down into primes (through Prime Factorization!)

For thousands of years number theory was considered a lofty subject, and finding prime factorizations would have been a mental workout akin to our doing Sudoku or Crossword puzzles. It wasn’t until we started creating machines that could count (and eventually machines that could connect us to countless videos of small, fluffy animals sneezing) that we found a practical use for prime factorization.

We noted that factoring big primes takes a while, students should have cursory familiarity with this idea, and created RSA cryptography based on this. Every now and again the RSA foundation would offer prize money for people to attempt to factorize some really big numbers. Prime factorization is even worth money (the RSA challenge in 1997 offered a \$200k prize for factoring something around RSA-380.)

# Cryptography As a Teaching Tool

From the webpage Cryptography As a Teaching Tool, found at http://www.math.washington.edu/~koblitz/crlogia.html, which was written by Dr. Neal Koblitz, Professor of Mathematics at the University of Washington:

Cryptography has a tremendous potential to enrich math education. In the first place, it puts mathematics in a dramatic setting. Children are fascinated by intrigue and adventure. More is at stake than a grade on a test: if you make a mistake, your agent will be betrayed.

In the second place, cryptography provides a natural way to get students to discover certain key mathematical concepts and techniques on their own. Too often math teachers present everything on a silver platter, thereby depriving the children of the joy of discovery. In contrast, if after many hours the youngsters finally develop a method to break a cryptosystem, then they will be more likely to appreciate the power and beauty of the mathematics that they have uncovered. Later I shall describe cryptosystems that the children can break if they rediscover such fundamental techniques of classical mathematics as the Euclidean algorithm and Gaussian elimination.

In the third place, a central theme in cryptography is what we do not know or cannot do. The security of a cryptosystem often rests on our inability to efficiently solve a problem in algebra, number theory, or combinatorics. Thus, cryptography provides a way to counterbalance the impression that students often have that with the right formula and a good computer any math problem can be quickly solved.

Mathematics is usually taught as if it were a closed book. Other areas of science are associated in children’s minds with excitement and mystery. Why did the dinosaurs die out? How big is the Universe? M. R. Fellows has observed that in mathematics as well, the frontiers of knowledge can and should be put within reach of young students.

Finally, cryptography provides an excellent opportunity for interdisciplinary projects… in the middle or even primary grades.

This webpage provides an excellent mathematical overview as well as some details about to engage students with the mathematics of cryptography.