1 | /*****************************************************************************\ |
---|
2 | * Computer Algebra System SINGULAR |
---|
3 | \*****************************************************************************/ |
---|
4 | /** @file misc_ip.h |
---|
5 | * |
---|
6 | * This file provides miscellaneous functionality. |
---|
7 | * |
---|
8 | * ABSTRACT: This file provides the following miscellaneous functionality: |
---|
9 | * - prime factorisation of bigints with prime factors < 2^31 |
---|
10 | * (This will require at most 256 MByte of RAM.) |
---|
11 | * - approximate square root of a bigint |
---|
12 | * |
---|
13 | * Most of the functioanlity implemented here had earlier been |
---|
14 | * coded in SINGULAR in some library. Due to performance reasons |
---|
15 | * these algorithms have been moved to the C/C++ kernel. |
---|
16 | * |
---|
17 | * @author Frank Seelisch |
---|
18 | * |
---|
19 | * |
---|
20 | **/ |
---|
21 | /*****************************************************************************/ |
---|
22 | |
---|
23 | #ifndef MISC_H |
---|
24 | #define MISC_H |
---|
25 | |
---|
26 | #include "kernel/mod2.h" |
---|
27 | |
---|
28 | #include "coeffs/si_gmp.h" |
---|
29 | #include "coeffs/coeffs.h" |
---|
30 | |
---|
31 | #include "Singular/lists.h" |
---|
32 | |
---|
33 | /** |
---|
34 | * Factorises a given bigint number n into its prime factors less |
---|
35 | * than or equal to a given bound, with corresponding multiplicities. |
---|
36 | * |
---|
37 | * The method finds all prime factors with multiplicities. If a positive |
---|
38 | * bound is given, then only the prime factors <= pBound are being found. |
---|
39 | * In this case, there may remain an unfactored portion m of n. |
---|
40 | * Also, when n is negative, m will contain the sign. If n is zero, m will |
---|
41 | * be zero. |
---|
42 | * The method returns a list L filled with three entries: |
---|
43 | * L[1] a list; L[1][i] contains the i-th prime factor of |n| as int or |
---|
44 | * bigint (sorted in ascending order), |
---|
45 | * L[2] a list; L[2][i] contains the multiplicity of L[1, i] in |n| as int |
---|
46 | * L[3] contains the remainder m as int or bigint, depending on the size, |
---|
47 | * |
---|
48 | * We thus have: n = L[1][1]^L[2][1] * ... * L[1][k]^L[2][k] * L[3], where |
---|
49 | * k is the number of mutually distinct prime factors (<= a provided non- |
---|
50 | * zero bound). |
---|
51 | * Note that for n = 0, L[1] and L[2] will be emtpy lists and L[3] will be |
---|
52 | * zero. |
---|
53 | * |
---|
54 | * @return the factorisation data in a SINGULAR-internal list |
---|
55 | **/ |
---|
56 | lists primeFactorisation( |
---|
57 | const number n, /**< [in] the bigint > 0 to be factorised */ |
---|
58 | const int pBound /**< [in] bound on the prime factors |
---|
59 | seeked */ |
---|
60 | ); |
---|
61 | |
---|
62 | |
---|
63 | |
---|
64 | #ifdef PDEBUG |
---|
65 | #if (OM_TRACK > 2) && defined(OM_TRACK_CUSTOM) |
---|
66 | // #include "kernel/polys.h" |
---|
67 | /* Needed for debug Version of p_SetRingOfLeftv, Oliver */ |
---|
68 | #include "kernel/structs.h" |
---|
69 | void p_SetRingOfLeftv(leftv l, ring r); |
---|
70 | #endif |
---|
71 | #endif |
---|
72 | |
---|
73 | #endif |
---|
74 | /* MISC_H */ |
---|