Describes how Euler Phi of a semi prime can be used to factor a semi prime and gives an approximation for Euler Phi for small numbers and sample C++ code.
Table of Contents
- Introduction
- Euler Phi and Factoring Semi-primes
- Approximating Euler Phi
- Considerations for large n
- Conclusion
Objectives and Key Themes
This article aims to demonstrate the significance of the Euler Phi function in factoring semi-primes and to provide an approximation for this function. It explores the relationship between Euler Phi and factoring semi-primes, and examines the effectiveness of an approximation for Euler Phi for different values of n.- Euler Phi function
- Factoring semi-primes
- Approximation of Euler Phi
- Considerations for large values of n
- Applications of Euler Phi in number theory
Chapter Summaries
Introduction
The article introduces the Euler Phi function and its application in factoring semi-primes. It explains that the function calculates the number of integers relatively prime to a given integer, with specific relevance to factoring semi-primes.Euler Phi and Factoring Semi-primes
This section explores the relationship between Euler Phi and factoring semi-primes. It presents a formula for computing Euler Phi for semi-primes and derives an expression for the sum of the prime divisors (p+q) of a semi-prime (n), based on Euler Phi and n. The section highlights the potential for developing a factoring algorithm using this relationship.Approximating Euler Phi
The chapter focuses on approximating the Euler Phi function, particularly for numbers that are the square of a prime number (p*p). It introduces an approximation formula for Euler Phi based on the square root of n and demonstrates its application for semi-primes. The text also provides a C++ code example to generate semi-primes and compute their Euler Phi values and approximations.Considerations for Large n
The article analyzes the accuracy of the approximation for large values of n. It emphasizes that the approximation becomes less accurate as the value of n increases, highlighting the limitations of the approximation for large semi-primes.Keywords
This article focuses on the Euler Phi function and its applications in factoring semi-primes. Key concepts include Euler Phi, semi-primes, prime factorization, approximation algorithms, and computational limitations. The study emphasizes the relationship between Euler Phi and prime factorization, explores the potential for developing factoring algorithms using Euler Phi, and examines the accuracy of an approximation for Euler Phi for different values of n.
Excerpt out of 10 pages
- scroll top
- Quote paper
- Dr. Roger Doss (Author), 2013, An Approximation for Euler Phi, Munich, GRIN Verlag, https://www.grin.com/document/208018
Look inside the ebook
