CERIAS - Center for Education and Research in Information Assurance and Security

Skip Navigation
CERIAS Logo
Purdue University
Center for Education and Research in Information Assurance and Security

Several Problems in Number Theory

Download

Download PDF Document
PDF

Author

Sangil Nahm

Tech report number

CERIAS TR 2011-02

Entry type

phdthesis

Abstract

For a long time, number theory has influenced information security and cryptography. This thesis adds examples of its influence. The first topic is related with Broadcast Group Key Management (BGKM) in cryptography. After the Access Control Polynomial (ACP) BGKM scheme was proposed, people tried to check its basic security properties in BGKM. They found that it has a weakness in the key hiding property by finding a counterexample when $p=2$. Here, we give strong evidence that it has a weakness in its key hiding property for all sufficiently large primes. The second topic is a well known integer factoring algorithm SQUFOF, which stands for SQUare FOrm Factorization, invented by Daniel Shanks. At present, SQUFOF is the fastest factoring algorithm for numbers between $10^$ and $10^$. In Gower's thesis, he made conjectures about the probability distribution of the number of forms that SQUFOF must examine before finding a proper square form and the number of forms enqueued during the factorization of $N$. We propose a different probability distribution (geometric rather than exponential) than did Gower, and we use Gower's data to support our conclusions. The third topic is the period of the Bell numbers $B(n)$ modulo a prime. It was proved by Williams that the minimum period of the sequence $\{B(n) \bmod ~p\}$, $n=0$, 1, 2, $\ldots$, divides $N_p=(p^p-1)/(p-1)$. In fact, the minimum period equals $N_p$ for every prime $p$ for which this period is known. Several people have conjectured that the minimum period is always $N_p$. This thesis presents a heuristic argument supporting the conjecture.

Download

PDF

Date

2011 – 5 – 1

Key alpha

Nahm

School

Purdue University

Publication Date

2011-05-01

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.