nx_u4096_mul.nx source
↩ module page · 136 lines · 4191 B
1// nx_u4096_mul.nx -- 4096x4096 -> 8192-bit schoolbook multiplication
2// + wide-buffer helpers. Mirrors nx_u2048_mul on 256-limb wide buffers.
3// Foundation for nx_rsa4096_mod (which Barrett-reduces against the
4// ISRG Root X1 4096-bit modulus).
5//
6// API:
7// u4096_wide_alloc() -> *i64 256-limb buffer (zeroed)
8// u4096_mul_wide(out_256, a, b) -- out = a * b (no reduction)
9// u4096_wide_shl1(out_256) -- in-place left shift by 1 bit
10// u4096_wide_get_bit(a_256, bit) -- bit 0..8191
11// u4096_wide_sub_low(out_256, sub_128) -- out[0..128) -= sub
12// u4096_wide_low_cmp(a_256, n_128) -- cmp low 128 limbs
13// u4096_wide_copy_low(out_128, src_256)
14//
15// license_tier: INDEPENDENT_REDERIVE
16// genealogy_id: international-research-sources/ietf/rfc_8017
17// lineage_id: nishi_u4096_mul_q1
18
19// nx_safety_envelope:
20// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
21// sil_target: SIL1
22// evidence: [u4096-wide-mul-for-rsa-4096-le-root]
23// verdict: NOT_YET_EVALUATED
24
25import "nx_syscalls.nx"
26import "nx_u4096.nx"
27
28const NX_U4096_WIDE_LIMBS: i64 = 256
29const NX_U4096_WIDE_BYTES: i64 = 1024
30
31func u4096_wide_alloc() -> *i64 {
32 let b: *u8 = sys_mmap(NX_U4096_WIDE_LIMBS * 8)
33 let p: *i64 = b as *i64
34 var i: i64 = 0
35 while i < NX_U4096_WIDE_LIMBS {
36 p[i] = 0
37 i = i + 1
38 }
39 return p
40}
41
42// out_256 = a * b (4096x4096 -> 8192). Aliasing: out_256 must be
43// distinct from a and b.
44func u4096_mul_wide(out_256: *i64, a: *i64, b: *i64) -> i64 {
45 var k: i64 = 0
46 while k < NX_U4096_WIDE_LIMBS {
47 out_256[k] = 0
48 k = k + 1
49 }
50 var i: i64 = 0
51 while i < NX_U4096_LIMBS {
52 let ai: i64 = a[i] & NX_U4096_LIMB_MASK
53 var carry: i64 = 0
54 var j: i64 = 0
55 while j < NX_U4096_LIMBS {
56 let bj: i64 = b[j] & NX_U4096_LIMB_MASK
57 let prev: i64 = out_256[i + j] & NX_U4096_LIMB_MASK
58 let s: i64 = prev + ai * bj + carry
59 out_256[i + j] = s & NX_U4096_LIMB_MASK
60 carry = (s >> NX_U4096_LIMB_BITS) & NX_U4096_LIMB_MASK
61 j = j + 1
62 }
63 out_256[i + 128] = carry
64 i = i + 1
65 }
66 return 0
67}
68
69// Left-shift a 256-limb wide buffer by 1 bit.
70// Returns the bit that fell off the top.
71func u4096_wide_shl1(out_256: *i64) -> i64 {
72 var i: i64 = 0
73 var carry: i64 = 0
74 while i < NX_U4096_WIDE_LIMBS {
75 let v: i64 = out_256[i] & NX_U4096_LIMB_MASK
76 let new_carry: i64 = (v >> 31) & 1
77 out_256[i] = ((v << 1) | carry) & NX_U4096_LIMB_MASK
78 carry = new_carry
79 i = i + 1
80 }
81 return carry
82}
83
84// Get bit i (0..8191) where bit 0 is LSB.
85func u4096_wide_get_bit(a_256: *i64, bit: i64) -> i64 {
86 let limb: i64 = bit / 32
87 let pos: i64 = bit % 32
88 return (a_256[limb] >> pos) & 1
89}
90
91// Subtract a u4096 from the low 128 limbs of the wide buffer.
92// out_256[0..128) -= sub[0..128). Returns borrow-out (0 or 1).
93func u4096_wide_sub_low(out_256: *i64, sub: *i64) -> i64 {
94 var i: i64 = 0
95 var borrow: i64 = 0
96 while i < NX_U4096_LIMBS {
97 let d: i64 = (out_256[i] & NX_U4096_LIMB_MASK) - (sub[i] & NX_U4096_LIMB_MASK) - borrow
98 if d < 0 {
99 out_256[i] = (d + (1 << NX_U4096_LIMB_BITS)) & NX_U4096_LIMB_MASK
100 borrow = 1
101 } else {
102 out_256[i] = d & NX_U4096_LIMB_MASK
103 borrow = 0
104 }
105 i = i + 1
106 }
107 return borrow
108}
109
110// Compare low 128 limbs of wide buffer against u4096 modulus.
111// Returns: -1 if a < n, 0 if equal, +1 if a > n.
112// (Assumes the high 128 limbs of a_256 are zero.)
113func u4096_wide_low_cmp(a_256: *i64, n: *i64) -> i64 {
114 var i: i64 = NX_U4096_LIMBS - 1
115 while i >= 0 {
116 let av: i64 = a_256[i] & NX_U4096_LIMB_MASK
117 let nv: i64 = n[i] & NX_U4096_LIMB_MASK
118 if av < nv { return 0 - 1 }
119 if av > nv { return 1 }
120 i = i - 1
121 }
122 return 0
123}
124
125func u4096_wide_copy_low(out_128: *i64, src_256: *i64) -> i64 {
126 var i: i64 = 0
127 while i < NX_U4096_LIMBS {
128 out_128[i] = src_256[i]
129 i = i + 1
130 }
131 return 0
132}
133
134func main() -> i64 {
135 return 0
136}