Factoring Techniques, MPN and FPN

Factoring Techniques, MPN and FPN
Updated 27 Sep 2004

No License

Fct_MPN_FPN_I4_Ch1_NK.zip contains the following :

MPN_FPN.m : This programme creates Mersenne Prime Numbers and Fermat Prime Numbers.
We are however, limited in the range here because MATLAB's isprime()is limited to only 2^32.

Prob5_Ch1_NK.m : This script describes the step-by-step procedure for solving problems similar to Prob 5 in P29 of the book :
A course in Number Theory and Cryptography by Neal Koblitz

Here, we find the factors of numbers (2^n + 1).
FPN (Fermat Prime Number) is of type (2^d + 1) where d is of a power of 2.

Prob 4 / P29 says that (2^n + 1) has prime factors which can be either of type (2^d + 1) or of type =eqvt mod (1, 2n)
In this file, we have considered those (2^d + 1) which happen to be FPN.
So, after dividing (2^n + 1) by FPN (normally, lcm of all (2^d + 1) s),
we call the routine find_Primes_1__mod_2n_mod_n.m to find the other factors.

Q-5a-FPN : Will (b^n + 1) have at the most just ONE FPN as a factor ?
Refer my analysis and explanation of the question in MPN_FPN.m

find_Primes_1__mod_2n_mod_n.m : This function can be used for finding prime factors restricted to type mod (p, 2n) = 1 or mod (p, n) = 1 ie, 1 =eqvt mod (p, 2n) or 1 =eqvt mod (p, n).
So, compared to factor() of MATLAB, the "left-out" primes will be those that are NOT of type
mod (p, 2n) = 1 or mod (p, n) = 1

Exc_I_4_P29_NK.m : This file has some notes as I went along solving the problems in Exercise I.4 / P29 of the book : A course in Number Theory and Cryptography by Neal Koblitz

Problems described in this file essentially use many of the techniques and principles described in Prob5_Ch1_NK.m

sort_with_single_entries.m : Matlab's sort "preserves" multiple entries in the list. So, I developed sort_with_single_entries.m to get a get sorted list which will have only single entries of each value.
Further, sort() is a built-in function, so it's difficult to make changes to incorporate this additional reqmt.

find_x_y__p_1_mod_6.m : This function finds x and y pairs of numbers such that x2 + 3y2 = p where mod(p, 6) = 1

Cite As

Sundar Krishnan (2024). Factoring Techniques, MPN and FPN (https://www.mathworks.com/matlabcentral/fileexchange/5920-factoring-techniques-mpn-and-fpn), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R13
Compatible with any release
Platform Compatibility
Windows macOS Linux
Find more on Encryption / Cryptography in Help Center and MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Version Published Release Notes