8.5. Running Time of the Naive Algorithm

Try these first

1. 1.

   What is a prime number?

   Hint

   Think about what makes a number prime.

2. 2.

   Up to what integer do we check divisibility to determine if a number is prime using the naive algorithm?

   Hint

   This relates to the definition of composite numbers.

3. 3.

   What defines a prime number?

   • A number greater than 1 with exactly two positive divisors.
   • Any odd number.
   • A numeral with no even divisors.

   Hint

   Focus on the divisors of the number.

4. 4.

   The naive algorithm checks divisibility up to which number?

   • The number itself
   • Its square root
   • Half of the number

   Hint

   Visualization of divisors helps with this.

5. 5.

   Create a comparison chart detailing time complexity and efficiencies between the naive algorithm and AKS.

   Hint

   Consider using a graph as a visual for this comparison.

6. 6.

   Explain how the inefficiency of the naive algorithm can impact cryptographic systems.

   Hint

   Connect the practical application of primes in security systems.