nx_u2048_mul.nx source
↩ module page · 131 lines · 3906 B
1// nx_u2048_mul.nx -- 2048x2048 -> 4096-bit schoolbook multiplication
2// + wide-buffer helpers. Mirrors nx_u256_mul/nx_u384_mul on 128-limb
3// wide buffers. Foundation for nx_rsa2048_mod.
4//
5// API:
6// u2048_wide_alloc() -> *i64 128-limb buffer (zeroed)
7// u2048_mul_wide(out_128, a, b) -- out = a * b (no reduction)
8// u2048_wide_shl1(out_128) -- in-place left shift by 1 bit
9//
10// license_tier: INDEPENDENT_REDERIVE
11// genealogy_id: international-research-sources/ietf/rfc_8017
12// lineage_id: nishi_u2048_mul_q10
13
14// nx_safety_envelope:
15// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
16// sil_target: SIL1
17// evidence: [bulk_applied_2026-05-20, u2048-wide-mul]
18// verdict: NOT_YET_EVALUATED
19
20import "nx_syscalls.nx"
21import "nx_u2048.nx"
22
23const NX_U2048_WIDE_LIMBS: i64 = 128
24const NX_U2048_WIDE_BYTES: i64 = 512
25
26func u2048_wide_alloc() -> *i64 {
27 let b: *u8 = sys_mmap(NX_U2048_WIDE_LIMBS * 8)
28 let p: *i64 = b as *i64
29 var i: i64 = 0
30 while i < NX_U2048_WIDE_LIMBS {
31 p[i] = 0
32 i = i + 1
33 }
34 return p
35}
36
37// out_128 = a * b (2048x2048 -> 4096). Aliasing: out_128 must be
38// distinct from a and b.
39func u2048_mul_wide(out_128: *i64, a: *i64, b: *i64) -> i64 {
40 var k: i64 = 0
41 while k < NX_U2048_WIDE_LIMBS {
42 out_128[k] = 0
43 k = k + 1
44 }
45 var i: i64 = 0
46 while i < NX_U2048_LIMBS {
47 let ai: i64 = a[i] & NX_U2048_LIMB_MASK
48 var carry: i64 = 0
49 var j: i64 = 0
50 while j < NX_U2048_LIMBS {
51 let bj: i64 = b[j] & NX_U2048_LIMB_MASK
52 let prev: i64 = out_128[i + j] & NX_U2048_LIMB_MASK
53 let s: i64 = prev + ai * bj + carry
54 out_128[i + j] = s & NX_U2048_LIMB_MASK
55 carry = (s >> NX_U2048_LIMB_BITS) & NX_U2048_LIMB_MASK
56 j = j + 1
57 }
58 out_128[i + 64] = carry
59 i = i + 1
60 }
61 return 0
62}
63
64// Left-shift a 128-limb wide buffer by 1 bit.
65// Returns the bit that fell off the top.
66func u2048_wide_shl1(out_128: *i64) -> i64 {
67 var i: i64 = 0
68 var carry: i64 = 0
69 while i < NX_U2048_WIDE_LIMBS {
70 let v: i64 = out_128[i] & NX_U2048_LIMB_MASK
71 let new_carry: i64 = (v >> 31) & 1
72 out_128[i] = ((v << 1) | carry) & NX_U2048_LIMB_MASK
73 carry = new_carry
74 i = i + 1
75 }
76 return carry
77}
78
79// Get bit i (0..4095) where bit 0 is LSB.
80func u2048_wide_get_bit(a_128: *i64, bit: i64) -> i64 {
81 let limb: i64 = bit / 32
82 let pos: i64 = bit % 32
83 return (a_128[limb] >> pos) & 1
84}
85
86// Subtract a u2048 from the low 64 limbs of the wide buffer.
87// out_128[0..64) -= sub[0..64). Returns borrow-out (0 or 1).
88func u2048_wide_sub_low(out_128: *i64, sub: *i64) -> i64 {
89 var i: i64 = 0
90 var borrow: i64 = 0
91 while i < NX_U2048_LIMBS {
92 let d: i64 = (out_128[i] & NX_U2048_LIMB_MASK) - (sub[i] & NX_U2048_LIMB_MASK) - borrow
93 if d < 0 {
94 out_128[i] = (d + (1 << NX_U2048_LIMB_BITS)) & NX_U2048_LIMB_MASK
95 borrow = 1
96 } else {
97 out_128[i] = d & NX_U2048_LIMB_MASK
98 borrow = 0
99 }
100 i = i + 1
101 }
102 return borrow
103}
104
105// Compare low 64 limbs of wide buffer against u2048 modulus.
106// Returns: -1 if a < n, 0 if equal, +1 if a > n.
107// (Assumes the high 64 limbs of a_128 are zero.)
108func u2048_wide_low_cmp(a_128: *i64, n: *i64) -> i64 {
109 var i: i64 = NX_U2048_LIMBS - 1
110 while i >= 0 {
111 let av: i64 = a_128[i] & NX_U2048_LIMB_MASK
112 let nv: i64 = n[i] & NX_U2048_LIMB_MASK
113 if av < nv { return 0 - 1 }
114 if av > nv { return 1 }
115 i = i - 1
116 }
117 return 0
118}
119
120func u2048_wide_copy_low(out_64: *i64, src_128: *i64) -> i64 {
121 var i: i64 = 0
122 while i < NX_U2048_LIMBS {
123 out_64[i] = src_128[i]
124 i = i + 1
125 }
126 return 0
127}
128
129func main() -> i64 {
130 return 0
131}