0
# Mathematical Primitives
1

2
Mathematical operations and data structures that form the foundation of PyCryptodome's cryptographic implementations. Provides big integer arithmetic, primality testing, and mathematical utilities optimized for cryptographic computations.
3

4
## Capabilities
5

6
### Big Integer Arithmetic
7

8
High-precision integer arithmetic supporting arbitrarily large numbers with optimized implementations for cryptographic operations.
9

10
```python { .api }
11
class Integer:
12
    """
13
    Big integer class with cryptographic optimizations.
14
    Auto-selects best available implementation (GMP, custom, or native).
15
    """
16
    
17
    def __init__(self, value):
18
        """
19
        Initialize Integer from various sources.
20
        
21
        Parameters:
22
        - value: int, bytes, hex string, or another Integer
23
        """
24
    
25
    # Arithmetic operations
26
    def __add__(self, other) -> 'Integer':
27
        """Addition: self + other"""
28
    
29
    def __sub__(self, other) -> 'Integer':
30
        """Subtraction: self - other"""
31
    
32
    def __mul__(self, other) -> 'Integer':
33
        """Multiplication: self * other"""
34
    
35
    def __pow__(self, exponent, modulus=None) -> 'Integer':
36
        """
37
        Exponentiation: self ** exponent [mod modulus]
38
        Optimized for cryptographic use with Montgomery ladder.
39
        """
40
    
41
    def __floordiv__(self, other) -> 'Integer':
42
        """Floor division: self // other"""
43
    
44
    def __mod__(self, other) -> 'Integer':
45
        """Modulus: self % other"""
46
    
47
    def __divmod__(self, other) -> tuple:
48
        """Division with remainder: divmod(self, other)"""
49
    
50
    # Bitwise operations
51
    def __and__(self, other) -> 'Integer':
52
        """Bitwise AND: self & other"""
53
    
54
    def __or__(self, other) -> 'Integer':
55
        """Bitwise OR: self | other"""
56
    
57
    def __xor__(self, other) -> 'Integer':
58
        """Bitwise XOR: self ^ other"""
59
    
60
    def __lshift__(self, n: int) -> 'Integer':
61
        """Left shift: self << n"""
62
    
63
    def __rshift__(self, n: int) -> 'Integer':
64
        """Right shift: self >> n"""
65
    
66
    # Comparison operations
67
    def __eq__(self, other) -> bool:
68
        """Equality: self == other"""
69
    
70
    def __lt__(self, other) -> bool:
71
        """Less than: self < other"""
72
    
73
    def __le__(self, other) -> bool:
74
        """Less than or equal: self <= other"""
75
    
76
    # Modular arithmetic
77
    def inverse(self, modulus) -> 'Integer':
78
        """
79
        Compute modular multiplicative inverse.
80
        
81
        Parameters:
82
        - modulus (Integer): Modulus value
83
        
84
        Returns:
85
        Integer: self^(-1) mod modulus
86
        
87
        Raises:
88
        ValueError: If inverse doesn't exist (gcd(self, modulus) != 1)
89
        """
90
    
91
    def gcd(self, other) -> 'Integer':
92
        """
93
        Compute greatest common divisor using Euclidean algorithm.
94
        
95
        Parameters:
96
        - other (Integer): Other integer
97
        
98
        Returns:
99
        Integer: gcd(self, other)
100
        """
101
    
102
    def lcm(self, other) -> 'Integer':
103
        """
104
        Compute least common multiple.
105
        
106
        Parameters:
107
        - other (Integer): Other integer
108
        
109
        Returns:
110
        Integer: lcm(self, other)
111
        """
112
    
113
    # Utility methods
114
    def size_in_bits(self) -> int:
115
        """Number of bits needed to represent this integer."""
116
    
117
    def size_in_bytes(self) -> int:
118
        """Number of bytes needed to represent this integer."""
119
    
120
    def is_odd(self) -> bool:
121
        """Check if integer is odd."""
122
    
123
    def is_even(self) -> bool:
124
        """Check if integer is even."""
125
    
126
    # Conversion methods
127
    def to_bytes(self, length=None, byteorder='big') -> bytes:
128
        """
129
        Convert to bytes representation.
130
        
131
        Parameters:
132
        - length (int): Target byte length (None for minimal)
133
        - byteorder (str): 'big' or 'little' endian
134
        
135
        Returns:
136
        bytes: Binary representation
137
        """
138
    
139
    @staticmethod
140
    def from_bytes(data: bytes, byteorder='big') -> 'Integer':
141
        """
142
        Create Integer from bytes.
143
        
144
        Parameters:
145
        - data (bytes): Binary data
146
        - byteorder (str): 'big' or 'little' endian
147
        
148
        Returns:
149
        Integer: Integer representation of bytes
150
        """
151
    
152
    def __int__(self) -> int:
153
        """Convert to Python int (may lose precision for very large numbers)."""
154
    
155
    def __str__(self) -> str:
156
        """Decimal string representation."""
157
    
158
    def __repr__(self) -> str:
159
        """Representation string."""
160
    
161
    def __hex__(self) -> str:
162
        """Hexadecimal string representation."""
163
    
164
    def __bool__(self) -> bool:
165
        """Boolean value (False only for zero)."""
166
```
167

168
### Primality Testing
169

170
Probabilistic and deterministic algorithms for testing whether integers are prime, essential for key generation and validation.
171

172
```python { .api }
173
def miller_rabin_test(candidate, iterations, randfunc=None):
174
    """
175
    Miller-Rabin probabilistic primality test.
176
    
177
    Parameters:
178
    - candidate (int): Integer to test for primality
179
    - iterations (int): Number of test iterations (higher = more accurate)
180
    - randfunc (callable): Random function for choosing test bases
181
    
182
    Returns:
183
    int: 0 if composite, 1 if probably prime
184
    """
185

186
def lucas_test(candidate):
187
    """
188
    Lucas probabilistic primality test.
189
    
190
    Parameters:
191
    - candidate (int): Odd integer to test (must be > 2)
192
    
193
    Returns:
194
    int: 0 if composite, 1 if probably prime
195
    """
196

197
def test_probable_prime(candidate, randfunc=None):
198
    """
199
    Combined primality test using multiple algorithms.
200
    
201
    Parameters:
202
    - candidate (int): Integer to test
203
    - randfunc (callable): Random function
204
    
205
    Returns:
206
    int: PROBABLY_PRIME if likely prime, COMPOSITE if definitely composite
207
    """
208

209
# Primality test result constants
210
COMPOSITE = 0
211
PROBABLY_PRIME = 1
212
```
213

214
## Usage Examples
215

216
### Big Integer Operations
217
```python
218
from Crypto.Math.Numbers import Integer
219

220
# Create integers from different sources
221
a = Integer(12345)
222
b = Integer("0xABCDEF", 16)  # From hex string
223
c = Integer(b"Hello", 256)   # From bytes
224

225
# Arithmetic operations
226
sum_val = a + b
227
product = a * b
228
power = a ** 100
229

230
# Modular arithmetic (common in cryptography)
231
modulus = Integer(2**256 - 1)  # Large prime-like number
232
mod_power = pow(a, b, modulus)  # Fast modular exponentiation
233
inverse = a.inverse(modulus)    # Modular inverse
234

235
# Bitwise operations
236
xor_result = a ^ b
237
shifted = a << 10
238

239
# Size operations
240
print(f"Bits needed: {a.size_in_bits()}")
241
print(f"Bytes needed: {a.size_in_bytes()}")
242
```
243

244
### RSA Key Generation Mathematics
245
```python
246
from Crypto.Math.Numbers import Integer
247
from Crypto.Math.Primality import test_probable_prime
248
from Crypto.Random import get_random_bytes
249

250
def generate_rsa_primes(bits):
251
    """Generate two RSA primes of specified bit length."""
252
    while True:
253
        # Generate random candidate
254
        random_bytes = get_random_bytes(bits // 8)
255
        candidate = Integer.from_bytes(random_bytes)
256
        
257
        # Ensure odd and correct bit length
258
        candidate |= (1 << (bits - 1))  # Set MSB
259
        candidate |= 1                  # Set LSB (make odd)
260
        
261
        # Test for primality
262
        if test_probable_prime(candidate) == PROBABLY_PRIME:
263
            return candidate
264

265
# Generate 1024-bit RSA primes
266
p = generate_rsa_primes(1024)
267
q = generate_rsa_primes(1024)
268
n = p * q  # RSA modulus
269

270
# Compute private exponent
271
e = Integer(65537)  # Common public exponent
272
phi_n = (p - 1) * (q - 1)
273
d = e.inverse(phi_n)  # Private exponent
274

275
print(f"Public key: (n={n}, e={e})")
276
print(f"Private key: (n={n}, d={d})")
277
```
278

279
### Modular Exponentiation for Encryption
280
```python
281
from Crypto.Math.Numbers import Integer
282

283
# RSA encryption/decryption example
284
n = Integer("0x9A7B2C3D...")  # RSA modulus
285
e = Integer(65537)            # Public exponent
286
d = Integer("0x1F2E3D...")   # Private exponent
287

288
# Message as integer (after proper padding)
289
message = Integer(b"Hello, World!")
290

291
# Encryption: ciphertext = message^e mod n
292
ciphertext = pow(message, e, n)
293

294
# Decryption: plaintext = ciphertext^d mod n  
295
decrypted = pow(ciphertext, d, n)
296

297
assert decrypted == message
298
```
299

300
### Elliptic Curve Point Operations
301
```python
302
from Crypto.Math.Numbers import Integer
303

304
# Simplified elliptic curve point addition (conceptual)
305
class ECPoint:
306
    def __init__(self, x, y, curve_p):
307
        self.x = Integer(x)
308
        self.y = Integer(y)
309
        self.p = Integer(curve_p)  # Prime modulus
310
    
311
    def double(self):
312
        """Point doubling on elliptic curve."""
313
        # Simplified formula: slope = (3*x^2) / (2*y) mod p
314
        numerator = (Integer(3) * self.x * self.x) % self.p
315
        denominator = (Integer(2) * self.y) % self.p
316
        slope = (numerator * denominator.inverse(self.p)) % self.p
317
        
318
        # New coordinates
319
        x3 = (slope * slope - Integer(2) * self.x) % self.p
320
        y3 = (slope * (self.x - x3) - self.y) % self.p
321
        
322
        return ECPoint(x3, y3, self.p)
323

324
# Example with P-256 curve
325
p256_prime = Integer(2**256 - 2**224 + 2**192 + 2**96 - 1)
326
point = ECPoint(
327
    0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296,
328
    0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5,
329
    p256_prime
330
)
331
doubled_point = point.double()
332
```
333

334
### Primality Testing in Practice
335
```python
336
from Crypto.Math.Primality import miller_rabin_test, test_probable_prime
337
from Crypto.Math.Numbers import Integer
338

339
# Generate and test potential primes
340
def find_next_prime(start_value):
341
    """Find next probable prime after start_value."""
342
    candidate = Integer(start_value)
343
    if candidate.is_even():
344
        candidate += 1  # Make odd
345
    
346
    while True:
347
        # Quick test with small iterations
348
        if miller_rabin_test(candidate, 10) == PROBABLY_PRIME:
349
            # More thorough test
350
            if test_probable_prime(candidate) == PROBABLY_PRIME:
351
                return candidate
352
        candidate += 2  # Check next odd number
353

354
# Find large prime
355
large_prime = find_next_prime(2**512)
356
print(f"Found prime: {large_prime}")
357
print(f"Bit length: {large_prime.size_in_bits()}")
358
```
359

360
### Number Conversion and Encoding
361
```python
362
from Crypto.Math.Numbers import Integer
363

364
# Various ways to create and convert integers
365
num = Integer(12345)
366

367
# Convert to different formats
368
hex_string = hex(num)           # "0x3039"
369
decimal_string = str(num)       # "12345"
370
bytes_big = num.to_bytes(4, 'big')      # b'\x00\x009'
371
bytes_little = num.to_bytes(4, 'little') # b'9\x00\x00'
372

373
# Reconstruct from bytes
374
from_big = Integer.from_bytes(bytes_big, 'big')
375
from_little = Integer.from_bytes(bytes_little, 'little')
376

377
assert from_big == num
378
assert from_little == num
379

380
# Handle large numbers
381
large_num = Integer(2**1024 - 1)
382
large_bytes = large_num.to_bytes()  # Minimal byte representation
383
print(f"Large number byte length: {len(large_bytes)}")
384
```
385

386
## Performance Considerations
387

388
### Implementation Selection
389
PyCryptodome automatically selects the best available big integer implementation:
390

391
1. **GMP (GNU Multiple Precision)**: Fastest, requires libgmp
392
2. **Custom C**: Fast, pure C implementation included with PyCryptodome  
393
3. **Pure Python**: Fallback, slower but always available
394

395
### Optimization Tips
396
- Use modular exponentiation `pow(base, exp, mod)` instead of `(base ** exp) % mod`
397
- Prefer `Integer` objects for repeated operations to avoid conversion overhead
398
- Use appropriate bit sizes for your security requirements
399
- Cache frequently used constants (like moduli) as `Integer` objects
400

401
### Memory Management
402
- `Integer` objects handle memory automatically
403
- Very large numbers may consume significant memory
404
- Consider the trade-off between precision and memory usage
405

406
## Security Considerations
407

408
### Cryptographic Quality
409
- Primality tests are probabilistic with configurable accuracy
410
- Use sufficient iterations for security-critical applications
411
- Miller-Rabin test with 64+ iterations provides high confidence
412

413
### Side-Channel Resistance
414
- Modular exponentiation uses Montgomery ladder for timing attack resistance
415
- Constant-time operations where possible
416
- Consider implementation-specific side-channel protections
417

418
### Random Number Dependencies
419
- Primality tests require cryptographically secure randomness
420
- Use system-provided randomness or `Crypto.Random`
421
- Ensure proper entropy for key generation
422

423
## Error Handling
424

425
- `ValueError`: Invalid mathematical operations (e.g., division by zero, no modular inverse)
426
- `TypeError`: Incompatible types for operations
427
- `OverflowError`: Results too large for representation (rare with arbitrary precision)
428
- `ZeroDivisionError`: Division or modulus by zero