1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
//! Montgomery arithmetic for `Copy`-bound types.
//!
//! Two algorithm families live under this module:
//!
//! - **R > N path**: textbook Montgomery construction. Pick `R` as the
//! smallest power of 2 greater than the modulus, precompute
//! `R⁻¹ mod N` and `N' = -N⁻¹ mod R`, transform values into
//! Montgomery form, multiply in the Mont domain, transform back.
//! Building blocks: [`compute_params`], [`to_mont`], [`from_mont`],
//! [`mul`].
//!
//! - **Wide-REDC path** (`R = 2^W` exactly the word width): the
//! complete-pipeline operations [`mod_mul`] and [`mod_exp`] use this
//! internally. Overflow-free for full-width moduli; no caller-visible
//! Montgomery params required.
//!
//! For the high-level type-safe surface, see
//! [`modmath::Field`](crate::Field) — Montgomery context with
//! lifetime-branded residues.
//!
//! ## N' computation method
//!
//! [`compute_params`] uses a default algorithm internally. To pick
//! between trial-search / extended-Euclidean / Hensel's lifting, use
//! [`compute_params_with_method`] with an explicit
//! [`crate::NPrimeMethod`] choice. (The complete pipelines [`mod_mul`]
//! and [`mod_exp`] use wide-REDC which mandates Newton; method
//! selection is meaningful only on the R>N building-block path.)
// R > N path building blocks
pub use cratebasic_compute_montgomery_params as compute_params;
pub use cratebasic_compute_montgomery_params_with_method as compute_params_with_method;
pub use cratebasic_from_montgomery as from_mont;
pub use cratebasic_montgomery_mul as mul;
pub use cratebasic_to_montgomery as to_mont;
// Wide-REDC complete-pipeline operations
pub use cratebasic_montgomery_mod_exp as mod_exp;
pub use cratebasic_montgomery_mod_exp_odd as mod_exp_odd;
pub use cratebasic_montgomery_mod_mul as mod_mul;
pub use cratebasic_montgomery_mod_mul_odd as mod_mul_odd;
/// Pre-reduced variants. Caller guarantees inputs are in `[0, m)`;
/// the input `% m` reduction step is skipped.
/// Constant-time variants. The complete-pipeline operations with
/// branchless conditional-subtract finalize via
/// `subtle::ConditionallySelectable`, removing the operand-magnitude
/// side-channel on the final reduction step.
///
/// **Only pre-reduced entries are exposed.** CT-over-base
/// requires a CT reduction primitive; `core::ops::Rem` is
/// hardware-variable on common embedded targets, so any wrapper that
/// internally reduced via `Rem` would leak the base magnitude.
/// Callers needing CT-over-base should:
///
/// - reduce the base externally via a CT primitive (e.g.
/// `Field::reduce` on the `Ct` personality, which composes the CT
/// wide-REDC reduction), then dispatch to
/// [`pre_reduced::mod_exp`](self::ct::pre_reduced::mod_exp); or
/// - use the high-level [`Field<T, Ct>::exp`](crate::Field::exp)
/// surface, which handles reduction + exponentiation as a single
/// end-to-end CT pipeline.
///
/// There is no `mod_mul_ct` here because the underlying source crate
/// hasn't published one (the CIOS path is the canonical CT-mul entry
/// point — see
/// [`cios_montgomery_mul_ct`](crate::montgomery::cios::cios_montgomery_mul_ct)).
///
/// # Operator contract
///
/// CT entry points never invoke plain `+` / `-` / `*` on the carrier,
/// and since const-num-traits 0.2 they no longer *bound* them either:
/// every overflow-relevant operation goes through an explicitly-named
/// trait (`WrappingAdd`/`WrappingSub`/`WrappingMul`, `BorrowingSub`,
/// `CtIsZero`, subtle's comparisons), each carrying its own `Output`.
/// A backend can satisfy the entire CT surface without implementing
/// `core::ops` arithmetic at all — panicking or mode-dispatched
/// operator impls elsewhere in the carrier are irrelevant here.
/// Wide-REDC primitives at the `R = 2^W` working width — by-value
/// operands, `Copy`-bound `T`. These are the building blocks the
/// [`mod_mul`] / [`mod_exp`] pipelines call internally; consumers
/// reach for them directly when implementing their own Montgomery
/// pipelines (PQC's `Mont` newtype pattern, RSA's `ModMathParams`).
///
/// For the reference-based variant suitable for non-`Copy` bigint
/// backends, see [`modmath::strict::montgomery::wide`](crate::strict::montgomery::wide).