Factoring Techniques, MPN and FPN

Factoring Techniques, MPN and FPN

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