# Implementation details of ModMulFastConst function

**URL:** <https://openfhe.discourse.group/t/implementation-details-of-modmulfastconst-function/2025>\
**Category:** Library Questions\
**Created:** [May 12, 2025, 3:47pm UTC](https://openfhe.discourse.group/t/implementation-details-of-modmulfastconst-function/2025 "2025-05-12T15:47:25Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![hionwi](https://avatars.discourse-cdn.com/v4/letter/h/46a35a/32.png) [@hionwi](https://openfhe.discourse.group/u/hionwi)\
**Post date:** [May 12, 2025, 3:47pm UTC](https://openfhe.discourse.group/t/implementation-details-of-modmulfastconst-function/2025/1 "2025-05-12T15:47:25Z")

</div>

In [code ModMulFastConst function](https://github.com/openfheorg/openfhe-development/blob/main/src/core/include/math/hal/intnat/ubintnat.h), according to the comments, the ModMulFastConst function comes from [https://arxiv.org/pdf/1205.2926.pdf](https://arxiv.org/pdf/1205.2926.pdf) (Dave Harvey, FASTER ARITHMETIC FOR NUMBER-THEORETIC TRANSFORMS). The algorithm is described in lines 5-7 of Algorithm 2.  
In the original paper,

 ![Snipaste_2025-05-12_23-46-35](https://canada1.discourse-cdn.com/flex031/uploads/openfhe/original/1X/bbc72ba5f7d71a6b8f1d819abbeb9bc5a134057d.png)  
Q ← ⌊W′T/β⌋  
But in the code, `NativeInt q = MultDHi(m_value, bInv.m_value) + 1;`  
Why add 1 at the end?

---

<div class="post-metadata">

**Author:** ![Caesar](https://yyz1.discourse-cdn.com/flex031/user_avatar/openfhe.discourse.group/caesar/32/63_2.png) [@Caesar](https://openfhe.discourse.group/u/Caesar)\
**Post date:** [May 12, 2025, 8:34pm UTC](https://openfhe.discourse.group/t/implementation-details-of-modmulfastconst-function/2025/2 "2025-05-12T20:34:42Z")

</div>

Q is a measure of how many p's did we overflow. Algorithm 2 approximates this value, potentially underestimating it by 1, while OpenFHE implementation overestimates it by 1.

In OpenFHE, Q is incremented by 1 to simplify the adjustment logic in Step 7. The comparison is done against 0, and the increment `yprime + p` is conditional, that is, not always executed.