Factorization Basis

A factorization basis is simply a set of distinct prime numbers \( B = \{p_1, p_2, ..., p_N\} \) used to factorize numbers.

In other words, when factoring a number, we only consider the primes in the chosen basis.

Example

If we define our basis as \( B = \{2,3,5\} \), this means we're only interested in numbers that can be expressed as products of these primes.

For instance, within this basis, we can factorize \( n = 30 = 2 \times 3 \times 5 \) or \( n = 18 = 3^2 \times 2 \), but we cannot factorize \( n = 21 = 3 \times 7 \) because 7 is not part of our basis.

B-Numbers Modulo n

A number is called a B-number modulo n if it can be fully factorized using only the primes in \( B \), under modulo \( n \).

Put simply, when we break it down into prime factors, only the primes from \( B \) should appear.

A Practical Example

Let’s take \( n = 77 \) as our modulus and use the basis \( B = \{7, 11\} \).

Now, we look for numbers that can be written as combinations of the factors \( 7 \) and \( 11 \), meaning numbers of the form:

\[ 7^a \cdot 11^b \]

The \( B \)-numbers modulo \( 77 \) are all numbers of this form, reduced modulo \( 77 \).

Here are a few examples:

• \( 1 = 7^0 \cdot 11^0 \)
• \( 7 = 7^1 \cdot 11^0 \)
• \( 11 = 7^0 \cdot 11^1 \)
• \( 49 = 7^2 \cdot 11^0 \)
• \( 77 = 7^1 \cdot 11^1 \)
• \( 121 = 7^0 \cdot 11^2 \)
• \( 343 = 7^3 \cdot 11^0 \)
• \( 539 = 7^1 \cdot 11^2 \)
• \( 847 = 7^2 \cdot 11^1 \)
• \( 1331 = 7^0 \cdot 11^3 \)
• etc.

So, a number \( m \) is a \( B \)-number modulo 77 if, when reduced modulo 77, it contains only factors from \( B \).

For instance, \( m=49 \) qualifies as a \( B \)-number since it contains only \( 7 \), which is in \( B \): \[ m = 49 \equiv 7^2 \pmod{77} \] On the other hand, \( m = 20 \) does not, because it contains the primes \( 2 \) and \( 5 \), which are not in \( B \): \[ m = 20 \equiv 2^2 \times 5 \pmod{77} \]

What Is a B-Vector?

The B-vector of a number \( m \) relative to a factorization basis \( B = \{p_1, p_2, ..., p_N\} \) is the vector of exponents \((\alpha_1, \alpha_2, ..., \alpha_N)\) in its factorization modulo \( n \): \[ m \equiv p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_N^{\alpha_N} \pmod{n} \]

In other words, the B-vector simply captures how many times each prime in \( B \) appears in the factorization of \( m \).

Example

Consider the factorization basis \( B = \{2, 3, 5\} \) and the number \( m = 18 \):

\[ m = 18 = 2^1 \cdot 3^2 \cdot 5^0 \]

Its B-vector is:

\[ v(m) = (1, 2, 0) \]

since the exponents of the prime factors are 1, 2, and 0.

Reducing Modulo 2

Given a number \[ m \equiv p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_N^{\alpha_N} \pmod{n} \] the modulo-2 reduction of its exponent vector \[ v(m) = ( \alpha_1, \alpha_2, \alpha_3 , ... , \alpha_N ) \] is obtained by replacing each exponent \( \alpha_i \) with its remainder when divided by 2: \[ \beta_i \equiv \alpha_i \pmod{2} \] This effectively replaces even values with 0 and odd values with 1: \[ w(m) = ( \beta_1, \beta_2, \beta_3, ... ) \]

Why is modulo-2 reduction useful? This transformation helps identify whether a number is a perfect square modulo \( n \). If all the exponents in the factorization of \( m \) are even, then \( m \) is a perfect square modulo \( n \).

Example

For \( m = 18 = 2^1 \cdot 3^2 \cdot 5^0 \) in the basis \( B = \{2, 3, 5\} \), the B-vector is:

\[ v(m) = (1, 2, 0) \]

Applying modulo-2 reduction:

\[ w(m) = (1, 0, 0) \]

Since not all exponents are even, \( m \) is not a perfect square.

Conversely, consider \( m = 4 = 2^2 \) in the same basis:

\[ v(m) = (2, 0, 0) \]

Reducing modulo 2:

\[ w(m) = (0, 0, 0) \]

Since all exponents are even, \( m \) is a perfect square.

This technique is crucial in applications such as cryptography, number theory, and integer factorization algorithms.

Finding a perfect square within a given basis is a bit like hunting for a good parking spot downtown—it’s doable, but you need a keen eye and a bit of patience. Modulo-2 reduction helps streamline the process.

And so the story goes...