This file is indexed.

/usr/include/givaro/givintsqrootmod.h is in libgivaro-dev 4.0.2-8ubuntu1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  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
// ============================================================= //
// Copyright(c)'1994-2009 by The Givaro group
// This file is part of Givaro.
// Givaro is governed by the CeCILL-B license under French law
// and abiding by the rules of distribution of free software.
// see the COPYRIGHT file for more details.
// Time-stamp: <16 Jun 15 16:05:06 Jean-Guillaume.Dumas@imag.fr>
// Author : Yanis Linge
// ============================================================= //


/** @file givintsqrootmod.h
 * @ingroup integers
 * @brief Modular square roots
 */

#ifndef __GIVARO_sqrtmod_H
#define __GIVARO_sqrtmod_H

#include <iostream>
#include "givaro/givinteger.h"
#include "givaro/givintprime.h"
#include "givaro/givintfactor.h"
#include "givaro/givintrns.h"
#include "givaro/givrandom.h"
#include "givaro/givpower.h"
#include <cmath>

namespace Givaro {

	//!  Modular square roots.
template < class MyRandIter = GivRandom >
class IntSqrtModDom:public IntFactorDom < MyRandIter > {
public:
    typedef IntFactorDom < MyRandIter > Father_t;
    typedef typename IntFactorDom < MyRandIter >::Rep Rep;

    IntSqrtModDom (MyRandIter g = MyRandIter ()) : IntFactorDom < MyRandIter > (g) {}

        // ======================================================== //
        // Modular Square root functions
        // ======================================================== //
    Rep & sqrootmod (Rep & x, const Rep & a, const Rep & n) const {
        std::vector < Rep > Lf;
        std::vector < uint64_t > Le;
        Father_t::set (Lf, Le, n);

        typename std::vector < Rep >::const_iterator Lf_iter = Lf.begin ();
        typename std::vector < uint64_t >::const_iterator Le_iter = Le.begin ();

        std::vector < Rep > roots;
        Rep tmp;

            // Build prime powers
        std::vector < Rep > Pe (Lf.size ());
        typename std::vector < Rep >::iterator Pe_iter = Pe.begin ();
        for (; Pe_iter != Pe.end (); ++Pe_iter, ++Lf_iter, ++Le_iter)
			dom_power (*Pe_iter, *Lf_iter, (long)*Le_iter, *this);

        Lf_iter = Lf.begin ();
        Le_iter = Le.begin ();
        Pe_iter = Pe.begin ();

            // roots mod powers of primes
        for (; Lf_iter != Lf.end (); ++Lf_iter, ++Le_iter, ++Pe_iter){
                // root mod a power of 2
            if (*Lf_iter == 2U){
                roots.push_back (
                    this->sqrootmodpoweroftwo (tmp, a, *Le_iter, *Pe_iter));
            } else {
                roots.push_back (
                    this->sqrootmodprimepower (tmp, a, *Lf_iter, *Le_iter, *Pe_iter));
            }
        }

            // Chinese Remaindering
        IntRNSsystem < std::vector, std::allocator > RNs (Pe);

        RNs.RnsToRing (x, roots);
        x = (x<0?-x:x);
        return x;
    }

        // ======================================================== //
        // Modular Square root sub-functions
        // ======================================================== //

        // p is supposed to be prime
    Rep & sqrootmodprime (Rep & x, const Rep & a, const Rep & p) const;

        // p is supposed to be prime, modulo is taken mod p^k
    Rep & sqrootmodprimepower (Rep & x, const Rep & a, const Rep & p, const uint64_t k, const Rep &pk) const;

        // modulo is taken mod 2^k
    Rep & sqrootmodpoweroftwo (Rep & x, const Rep & a,const uint64_t k, const Rep & pk) const;

protected:

        // ======================================================== //
        // Linear update using only onemorelift
        // ======================================================== //

        // p is supposed to be prime and odd
    Rep & sqrootlinear (Rep & x, const Rep & a,const Rep & p,const uint64_t k) const;

        // result is modulo 2^{k+1}
    Rep & sqroottwolinear(Rep & x, const Rep & a,const uint64_t k) const;

        // ======================================================== //
        // Liftings
        // ======================================================== //

        // PRECONDITION: x^2 = a [p^k]
        // RETURNS: x s.t. x^2 = a [p^{2k}]
    Rep & sqroothensellift (Rep & x, const Rep & a, const Rep & p, const uint64_t k, const Rep & pk) const;

        // PRECONDITION: x^2 = a [p^k]
        // RETURNS: x s.t. x^2 = a [p^{k+1}]
    Rep & sqrootonemorelift (Rep & x, const Rep & a, const Rep & p, const uint64_t k, const Rep & pk) const;

        // PRECONDITION: x^2 = a [2^k], with k>=3, a and x are odd
        // RETURNS: x s.t. x^2 = a [2^{2k-2}]
    Rep & sqrootmodtwolift (Rep & x, const Rep & a, const uint64_t k, const Rep & pk) const;

};

} // Givaro

#include "givaro/givintsqrootmod.inl"

#endif // __GIVARO_sqrtmod_H