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
References
Appendix
Research Objective and Scope
The primary objective of this work is to explore the relationship between the Euler Phi function and the factorization of semi-prime numbers, ultimately proposing an approximation method for the Euler Phi function to facilitate factoring processes.
- Mathematical analysis of the Euler Phi function in relation to semi-primes.
- Development of a factoring algorithm utilizing the Euler Phi function.
- Investigation into polynomial time approximations for Euler Phi.
- Empirical evaluation of the approximation accuracy for varying sizes of integers.
- Implementation of C++ and Pari/GP code for algorithm demonstration.
Excerpt from the Book
Euler Phi and Factoring Semi-primes
The definition of Euler Phi of n where n is a semi-prime is given by the formula :=
(p-1)(q-1) = (n)
Multiplying the terms, we then have :=
pq - p -q +1 = (n)
Solving for pq, we then have :=
pq = (n) + p + q + 1
Note that pq is n as n is the product of p and q, therefore :=
n = (n) + p + q + 1
Now, letting x = p + q, we can write that n is :=
n = (n) + x + 1
Finally, solving for x, gives :=
x = n - (n) + 1 (Equation 1)
Thus, x = p + q is equal to n – (n) + 1.
Summary of Chapters
Introduction: This chapter defines semi-prime numbers and introduces the Euler Phi function as a potential tool for integer factorization.
Euler Phi and Factoring Semi-primes: The text derives a mathematical relationship between a semi-prime n, its factors p and q, and the Euler Phi value, resulting in a quadratic equation format.
Approximating Euler Phi: The author discusses the complexity of computing Euler Phi and proposes an approximation formula based on the square root of n.
Considerations for large n: This section evaluates the limitations of the proposed approximation when applied to larger integers and demonstrates the growing discrepancy.
Conclusion: The author summarizes that while Euler Phi enables trivial factorization of semi-primes, the proposed approximation is primarily effective for smaller values.
References: This section lists the academic and technical sources utilized for the research.
Appendix: The appendix provides the full source code for the factoring algorithm and the sieve implementation used in the study.
Keywords
Euler Phi, Semi-prime, Factorization, Prime numbers, Quadratic formula, Polynomial time, Approximation, Integer, Sieve, Algorithm, Pari/GP, C++, Number theory, Computation, Mathematical modeling
Frequently Asked Questions
What is the core subject of this paper?
The paper examines the utility of the Euler Phi function in the factorization of semi-prime numbers and proposes an approximation method for this function.
What are the central topics discussed?
The primary topics include the mathematical definition of semi-primes, the relationship between Euler Phi and prime factors, and the implementation of computational algorithms to test these mathematical theories.
What is the primary research goal?
The goal is to determine if an approximation for the Euler Phi function can assist in the efficient factorization of semi-prime numbers.
Which scientific method is applied here?
The research uses algebraic derivation to create a factoring formula, followed by computational implementation and empirical testing using C++ and Pari/GP.
What is covered in the main body of the work?
The main body focuses on deriving the relationship between n, Euler Phi, and its factors, designing a factoring algorithm, and analyzing the accuracy of an approximation formula.
Which keywords best describe this research?
Key terms include Euler Phi, Semi-prime, Factorization, Approximation, and Computational Complexity.
How does the Euler Phi function relate to the quadratic formula in this study?
The study shows that by using the Euler Phi of a semi-prime, one can express the sum of the prime factors (p+q) in terms of n and Euler Phi, which fits into a quadratic equation that can be solved to retrieve p and q.
Why does the approximation method fail for large numbers?
The approximation relies on the assumption that p and q are close to the square root of n; as n increases, the variance between the factors increases, leading to a larger deviation in the approximation.
What is the role of the appendix?
The appendix provides the technical implementation, specifically C++ code for the factoring algorithm and the sieve, allowing for the verification and reproducibility of the provided findings.
- Quote paper
- Dr. Roger Doss (Author), 2013, An Approximation for Euler Phi, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/208018
