Some possible UROP or Master’s projects

1 **Smooth Numbers**.

Many factoring algorithms require one to find numbers in some range with
only small prime divisors. This has lead to the study of such numbers.
A number with all prime divisors less than x is called x-smooth. For example,
the 10 smooth numbers up to 100 are:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27,
28, 30, 32, 35, 36, 40, 42, 45, 48, 49, 50, 54, 56, 60, 63, 64, 70, 72, 75,
80, 81, 84, 90, 96, 98, 100.

There are 46 such numbers. This sounds like a lot: almost half of these
numbers is 10 smooth. But now they start getting rarer: there are 140
10 smooth numbers up to 1000 fraction: .14 , there are 332 up to 10,000
fraction: .0322 , and 587 up to 100,000 fraction .00587 .

It is known that this fraction is, in general, very regular: if f(n,
x) is the fraction of n smooth integers up to n^{
x} , then f(n, x) approximately satisfies the
differential delay equation

f(n, x) = 1,
if x <= 1,

f '(n, x) = -
f(n, x-1)/x, if x > 1,

and the approximation gets better as n gets bigger.

Recently, I have gotten interested in numbers that are “smooth” with
respect to some set of primes. For example, suppose we have the set of
primes 2, 5, 7 , and we want all numbers less than 100 which have only
these primes as divisors. The list is:

1, 2, 4, 5, 7, 8, 10, 14, 16, 20, 25, 28, 32, 35, 40, 49, 50, 56, 64,
70, 80, 98, 100.

Now there are only 23 such numbers, and there are only 56 of these numbers
up to 1000.

This project would be to investigate properties of numbers which are
smooth with respect to a set of primes, or with respect to multiple sets
of primes. In particular, it appears that there are functions like f
that tell approximately how many such numbers there should be.

2) **Carmichael numbers**.

It is known that there are infinitely many Carmichael numbers. In fact,
if C(x) is the number of Carmichael numbers < x, then it has been proven
that C(x) > x^{2/7}
, for all x sufficiently large. It is conjectured that for each e >
0, there is an N for which C(x) > x^{1-}^{
e} for all x > N. In particular, there should
be an N for which C(N) > sqrt(N). The goal of this project would be
to find such an N. (One of the reasons: Many mathematicians are, or were,
skeptical of this claim.)

Erdos’s approach: Let M be a highly composite number. For example,
we might use M = lcm(1, 2, , n) for some integer n. Let P be the
set of primes P = {p : p does not divide M but p - 1 does divide M}.
Carmichael number. If such products are uniformly distributed among the
reduced residue classes of M (as would be expected , then we should
Modifications on this approach support the conjecture that C(x) >
x^{ 1-}^{e}.

3) **Find a number which is both a base 2 pseudoprime and a
Fibonacci pseudoprime**.

This is a problem of Pomerance, Selfridge and Wagstaff, and carries a cash reward of $620 to the first one discovered!

If p is a prime, then a

If F

Thus, the goal of this project would be to find a nonprime number n such that n = 2 or 3 mod 5, 2

4)

a) Setting up the Bailey, Borwein and Plouffe formula to

calculate n’th hex digit without having calculated

previous digits.

The formula:

b) Finding similar formulas for pi and other constants.

that have nice simplifications. Of course, this trick works for numbers other than 8.

5)

and largest prime divisor of a number

An easy argument based on the above says that the largest prime divisor of a random number n should be about n

6)

This algorithm is a variation on Pollard’s p-1 method. In the p-1 method, one takes a large number M with lots of factors (a common choice is M = lcm(1, 2, 3, ... , k) for some suitable k) and calculates gcd (2

In the elliptic curve algorithm, we use a similar idea, except that we use the group of an elliptic curve mod p to do our calculations, rather than the group U(p). That is, by Lagrange’s theorem, if G is a group of order m, then for any element a of the group, a

7)

The quadratic sieve factoring algorithm is an algorithm for factoring a large number N. It involves the following steps:

(1) Select a “Base” of primes to use later on. For each of these primes, p must have the property that N = a

f(x) = x

(3) Using basic linear algebra, find several sequences of x such

unlucky and this gcd is 1 or N, use a different sequence found in step 3. Thus, if we found 10 such sequences in step 3, this would give us 10 chances to factor N.

a) Large prime variation

In this variation of the algorithm described above, in step 2, keep track of those x for which f(x) factors completely over the base OR f(x) factors completely except that one “large” prime factor of f(x) is outside the base. If we found x

b) Multiple polynomial method

B

c) Number field sieve

8)

Symmetric chain decompositions of B

A chain is symmetric if it starts and ends the same distance from the middle of the poset. So, for example, the chain 0100 0110 0111 starts one level below the middle and ends one lever above the middle. A symmetric chain decomposition is a partitioning of the poset so that every element is on some symmetric chain. For B

It is known that I_{1}
, I_{2}, I_{
3}, I_{4}
, I_{5}, and I_{
6} have symmetric chain decompositions. It
is not known if any higher ones do. A student of mine working on a 286
machine in the 1980’s was the first to do the cases of I_{
5}_{ }and I_{
6}.

9) **Calculations related to Goldbach’s 2 and 3-primes conjectures**
.

Goldbach’s 2 and 3-prime conjectures: Every even number
> 2 is the sum of two primes, every odd number > 5 is the sum of three
primes. This project would involve verifying the 3-primes conjecture up
to some bound B. Current best is, I believe, 10^{
20}. Also, I think the three primes conjecture
has been proved unconditionally for numbers > 10^{
46}?) then by constructing a chain of primes p_{
1}, p_{2}
, ... , p_{m}, with
p_{1} < C, p_{
m} > B, and p_{i}
- p_{i-1} < C, we
verify that the 3-primes conjecture is true up to B.

The way I did this for B = 10^{20}
: I looked for primes of the form

n(k, j) = 2^{34}(2^{
12}k + j) + 1. That is, for each k, I found
a j for which n(k, j) is prime. The form of the number n(k, j) facilitated
in the proof that it was prime: all that was needed was to find a number
a for which a^{(n-1)/2 }
= -1 (mod n).

10) **Prime proving algorithms**.

The project would be to implement one or more of the newer prime proving
algorithms on a workstation.