Week 04: Homework 3 - Introductory Programming in Java Skip navigation Introductory Programming in Java ANU College of Engineering & Computer Science Search query Search ANU web, staff & maps Search COMP6700 Lectures Labs Assignments menu Search query Search ANU web, staff & maps Search Search COMP6700 labs Week 01: Welcome Week 02: Lab 1 Week 03: Lab 2 and HW 1 Week 04: Lab 3 and HW 2 Week 05: Drop-in Lab, HW 3 Week 06: Lab 4 and HW 4 Week 07: Mid-sem Exam Week 08: Free (Anzac Day) Week 09: Lab 5 and HW 5 Week 10: Lab 6 and HW 6 Week 11: Lab 7 and HW 7 Week 12: Lab 8 and HW 8 related sites Wattle Piazza Week 04: Homework 3 Prime Factorisation The Problem It is a fact that any integer not equal to zero has a unique factorisation as product of primes. But finding this unique factorisation can take a very long time for large numbers. This principle is behind some important cryptographic algorithms such as the RSA algorithm. It is worthwhile to take a look at the following site to learn about prime factorisation. In particular, examples 1 and 2 of this site http://www.mathsisfun.com/prime-factorization.html demonstrate an algorithm which you might like to use in coding this homework. Your task for this homework exercise is to write a Java program that takes an integer as its command-line argument and prints out the complete prime factorisation of that integer, with the factors in ascending order. Your class must have at least one other method in addition to your main method. Your output needs to look similar to the example below. You do not have to do any other data checking. In other words, you may assume that the user will type in a non-negative integer, and that it’s OK if your program crashes if they type in something else. You also do not have to worry about your program working for very big integers; just use long variables rather than the BigInteger class as in Homework 2. Here is a sample run of such a program. Try to format your output as much like this as possible: % java Factors 15
15 = 1 * 3 * 5
% java Factors 2008
2008 = 1 * 2 * 2 * 2 * 251
% java Factors 1999817
1999817 = 1 * 1999817
(that's a prime number)
When you will have completed your Java program, test it on a few numbers until you are sure of its correctness. (Once again, don’t worry if your program gives bad results for very large integers.) There are some excellent web sites which discuss cryptography and explain how prime factorisation is used. The “Art of the Problem” cryptography series looks pretty good: https://www.youtube.com/watch?v=lICOtR078Gw. Further Programming Ideas Fermat Little Theorem, Primality Tests and Carmichael Numbers The primality test for an integer number N based on the factorisation is too inefficient for practice. Its complexity is O(2(log N)/2), and if N is large (like in RSA algorithms — 200-digit or more), the time for completing the algorithm like you tried above is ridiculously long. One of the methods used in practical applications is based of the so-called Little Fermat Theorem (LFT): If p is prime, then ap-1 - 1 is divisible by p for any 0 < a < p. In an equivalent form: If p is prime, then ap-1 = 1 mod p is divisible by p for any 0 < a < p. The number a is called a witness. Write a method fermatTest(long N, long a) which will test the equality featured in the (second) form of the LFT. If you implement the operation of raising a number to a power (which is less then this number) using the Egyptian multiplication algorithm (it has different names, look up the details online) with the efficiency of O(log N), the efficiency of the primality test will be fast (give the big-O expression!). It’s all good, but the trouble is that some non-prime numbers also pass the test — it’s “if” but not “iff”. These are called Carmichael numbers. Their definition is: A composite number N > 1 is called Carmichael number iff (if and only if) for every b > 1, which is coprime to N (b and N have no common prime factors) it follows that bN-1 = 1 mod N For example, 1722081 = 7 * 13 * 31 * 61 is a Carmichael number. Write a method boolean isCarmichael(long N). Find the first seven Carmichael numbers using the above method. Final Note The LFT and Carmichael tests are still rather inefficient for testing primality. In real application, a random test, like Miller-Rabin, is used; it gives the answer with non-absolute but very high probability that a number is prime, and it gives it very fast. You do not have to complete this part to get the maximum mark for this homework. Assessment You will get up to two marks, if you present a solution to the Homework exercise during the next week lab, or submitted it by push you GitLab repository as explained in the Forking your GitLab repository exercise (part of the Lab 4). Updated: 20 Mar 2017/ Responsible Officer: Head of School/ Page Contact: Alexei Khorev Contact ANU Copyright Disclaimer Privacy Freedom of Information +61 2 6125 5111 The Australian National University, Canberra CRICOS Provider : 00120C ABN : 52 234 063 906 You appear to be using Internet Explorer 7, or have compatibility view turned on. Your browser is not supported by ANU web styles. » Learn how to fix this » Ignore this warning in future
