text:
Batch NFS
This paper shows, assuming standard heuristics regarding the number-field sieve, that a "batch NFS" circuit of area \(L^{1.181\ldots +o(1)}\) factors \(L^{0.5+o(1)}\) separate \(B\)-bit RSA keys in time \(L^{1.022\ldots +o(1)}\). Here \(L=\exp ((\log 2^B)^{1/3}(\log \log 2^B)^{2/3})\). The circuit's area-time product (price-performance ratio) is just \(L^{1.704\ldots +o(1)}\) per key. For comparison, the best area-time product known for a single key is \(L^{1.976\ldots +o(1)}\).
This paper also introduces new "early-abort" heuristics implying that "early-abort ECM" improves the performance of batch NFS by a superpolynomial factor, specifically \(\exp ((c+o(1))(\log 2^B)^{1/6}(\log \log 2^B)^{5/6})\) where \(c\) is a positive constant.
KeywordsInteger factorization Number-field sieve Price-performance ratio Batching Smooth numbers Elliptic curves Early aborts
1 Introduction
The cryptographic community reached consensus a decade ago that a 1024-bit RSA key can be broken in a year by an attack machine costing significantly less than \(10^9\) dollars. See [51], [38], [24], and [23]. The attack machine is an optimized version of the number-field sieve (NFS), a factorization algorithm that has been intensively studied for twenty years, starting in [36]. The run-time analysis of NFS relies on various heuristics, but these heuristics have been confirmed in a broad range of factorization experiments using several independent NFS software implementations: see, e.g., [29], [30], [31], and [4].
signed by that domain's 1024-bit "zone-signing key", which in turn is
signed by that domain's 2048-bit "key-signing key", which in turn is
signed by .org's 1024-bit zone-signing key, which in turn is
signed by .org's 2048-bit key-signing key, which in turn is
signed by the DNS root's 1024-bit zone-signing key, which in turn is
signed by the DNS root's 2048-bit key-signing key.
A report [41] last year indicated that, out of the 112 top-level domains using DNSSEC, 106 used the same key sizes as .org. We performed our own survey of zone-signing keys in September 2014, after many new top-level domains were added. We found 286 domains using 1024-bit keys; 4 domains using 1152-bit keys; 192 domains using 1280-bit keys; and just 22 domains using larger keys. Almost all of the 1280-bit keys are for obscure domains such as .boutique and .rocks; high-volume domains practically always use 1024-bit keys.
A typical RSA key is believed to be worth less than the cost of the attack machine.
Building the attack machine means building a huge farm of application-specific integrated circuits (ASICs). Standard computer clusters costing the same amount of money are believed to take much longer to perform the same calculations.
It is believed that switching RSA signature keys after (e.g.) a month will render the attack machine useless, since the attack machine requires a full year to run.
DNSSEC signing keys should be large enough to avoid all known cryptographic attacks during the effectivity period of the key. To date, despite huge efforts, no one has broken a regular 1024-bit key; in fact, the best completed attack is estimated to be the equivalent of a 700-bit key. An attacker breaking a 1024-bit signing key would need to expend phenomenal amounts of networked computing power in a way that would not be detected in order to break a single key. Because of this, it is estimated that most zones can safely use 1024-bit keys for at least the next ten years.
This quote illustrates the first and third beliefs reported above: the attack cost would be "phenomenal" and would break only "a single key"; furthermore, the attack would have to be completed "during the effectivity period of the key". A typical DNSSEC key is valid for just one month and is then replaced by a new key.
"Many": The attacker is faced not with a single target, but with many targets. The algorithmic task here is not merely to break, e.g., a single 1024-bit RSA key; it is to break more than one hundred 1024-bit RSA keys for DNSSEC top-level domains, many more 1024-bit RSA keys at lower levels of DNSSEC, millions of 1024-bit RSA keys in SSL (as in [25], and [35]; note that upgrading SSL to 2048-bit RSA does nothing to protect the confidentiality of previously recorded SSL traffic), etc. This is important if there are ways to share attack work across the keys.
"Price-performance ratio": As in [53], [18], [50], [15], [54], [7], [51], [56], [23], [24], etc., our main interest is not in the number of "operations" carried out by an algorithm, but in the actual price and performance of a machine carrying out those operations. Parallelism increases price but often improves performance; large storage arrays are a problem for both price and performance. We use price-performance ratio as our primary cost metric, but we also report time separately since signature-key rotation puts a limit upon time.
"Asymptotic": The cost improvements that we present are superpolynomial in the size of the numbers being factored. We thus systematically suppress all polynomial factors in our cost analyses, simplifying the analyses.
For comparison (see Table 1.4), the best area-time product known for factoring a single key (without quantum computers) is \(L^{1.976\ldots +o(1)}\), even if non-uniform precomputations such as Coppersmith's "factorization factory" are allowed. The literature is reviewed below.
This paper also looks more closely at the \(L^{o(1)}\). The main bottleneck in batch NFS is not traditional sieving, but rather low-memory factorization, motivating new attention to the complexity of low-memory factorization. Traditional ECM, the elliptic-curve method of recognizing \(y\)-smooth integers, works in low memory and takes time \(\exp (\sqrt{(2+o(1)){\log y\log \log y}})\). One can reasonably guess that, compared to traditional ECM, "early-abort ECM" saves a subexponential factor here, but the complexity of early-abort ECM has never been analyzed. Section 3 of this paper introduces new early-abort heuristics implying that the complexity of early-abort ECM is \(\exp \left( \sqrt{\left( {8\over 9}+o(1)\right) {\log y\log \log y}}\right) \). Using early aborts increases somewhat the number of auxiliary integers that need to be factored, producing a further increase in cost, but the cost is outweighed by the faster factorization.
The ECM cost is obviously bounded by \(L^{o(1)}\): more precisely, the cost is \(\exp (\varTheta ((\log N)^{1/6}(\log \log N)^{5/6}))\) in the context of batch NFS, since \(y\in L^{\varTheta (1)}\). This cost is invisible at the level of detail of \(L^{1.704\ldots +o(1)}\). The speedup from ECM to early-abort ECM is nevertheless superpolynomial and directly translates into the same speedup in batch NFS.
Users comparing the value of an RSA key to the cost of an attack machine need to know the per-key cost of batch NFS. This has not been seriously studied. What the literature has actually studied in detail is the cost of NFS attacking one key at a time; this is not the same question. Our asymptotic results do not rule out the possibility that these costs are the same for 1024-bit RSA, but there is also no reason to be confident about any such possibility.
Most of the literature on single-key NFS relies heavily on operations that—for large key sizes—are not handled efficiently by current CPUs and that become much more efficient on ASICs: consider, for example, the routing circuit in [51]. Batch NFS relies much more heavily on massively parallel elliptic-curve scalar multiplication, exactly the operation that is shown in [12], [11], and [17] to fit very well into off-the-shelf graphics cards. The literature supports the view that off-the-shelf hardware is much less cost-effective than ASICs for single-key NFS, but there is no reason to think that the same is true for batch NFS.
The natural machine size for batch NFS (i.e., the circuit area if price-performance ratio is optimized) is larger than the natural machine size for single-key NFS, but the natural time is considerably smaller. As above, these asymptotic results undermine any confidence that one can obtain from comparing the natural time for single-key NFS to the rotation interval for signature keys: there is no reason to think that the latency of batch NFS will be as large as the latency of single-key NFS. Note that, even though this paper emphasizes optimal price-performance ratio for simplicity, there are also techniques to further reduce the time below the natural time, hitting much lower latency targets without severely compromising price-performance ratio: in particular, for the core sorting subroutines inside linear algebra, one can replace time \(T\) with \(T/f\) at the expense of replacing area \(A\) with \(Af^2\).
There are many other examples of cryptosystems where the attack cost does not grow linearly with the number of targets. For example, it is well known that exhaustive search finds preimages for \(U\) hash outputs in about the same time as a preimage for a single hash output; furthermore, the first preimage that it finds appears after only \(1/U\) of the total time, reducing actual security by \(\lg U\) bits. However, most cryptosystems have moved up to at least a "\(128\)-bit" security level, giving them a buffer against losing some bits of security. RSA is an exception: its poor performance at high security levels has kept it at a bleeding-edge "80-bit security" level. Even when users can be convinced to move away from 1024-bit keys, they normally move to \({\le }\)2048-bit keys. We question whether it is appropriate to view 1024-bit keys as "80-bit" security and 2048-bit keys as "112-bit" security if the attacker's costs per key are not so high.
1.3 Previous work. In the NFS literature, as in the algorithm literature in general, there is a split between traditional analyses of "operations" (adding two \(64\)-bit integers is one "operation"; looking up an element of a \(2^{64}\)-byte array is one "operation") and modern analyses of more realistic models of computation. We follow the terminology of our paper [14]: the "RAM metric" counts traditional operations, while the "\(AT\) metric" multiplies the area of a circuit by the time taken by the same circuit.
Buhler, H. Lenstra, and Pomerance showed in [19] (assuming standard NFS heuristics, which we now stop mentioning) that NFS factors a single key \(N\) with RAM cost \(L^{1.922\ldots +o(1)}\). As above, \(L\) means \(\exp ((\log N)^{1/3}(\log \log N)^{2/3})\). This exponent \(1.922\ldots \) is the most frequently quoted cost exponent for NFS.
Asymptotic exponents for several variants of NFS, assuming standard heuristics. "Exponent" \(e\) means asymptotic cost \(L^{e+o(1)}\) per key factored. "Precomp" \(2\theta \) means that there is a precomputation involving integer pairs \((a,b)\) up to \(L^{\theta +o(1)}\), for total precomputation cost \(L^{2\theta +o(1)}\); algorithms without precomputation have \(2\theta =0\). "Batch" \(\beta \) means batch size \(L^{\beta +o(1)}\); algorithms handling each key separately have \(\beta =0\). See Sect. 2 for further details.
\(1.976\ldots \)
2001 Bernstein [7]
RAM (unrealistic)
\(1.922\ldots \)
1993 Buhler–H. Lenstra–Pomerance [19]
RAM (unrealistic)
\(1.901\ldots \)
1993 Coppersmith [20]
\(1.900\ldots \)
batch NFS; this paper
\(1.829\ldots \)
batch NFS; this paper
\(1.763\ldots \)
batch NFS; this paper
\(1.710\ldots \)
batch NFS; this paper
\(1.704\ldots \)
batch NFS; this paper
RAM (unrealistic)
\(1.638\ldots \)
\(2.006\ldots \)
1993 Coppersmith [20]
The bottleneck in [19] is sieving, while the bottleneck in [20] is ECM. Both of these algorithms use \(L^{o(1)}\) operations in the RAM metric, but the \(o(1)\) is considerably smaller for sieving than for ECM.
Even if the \(o(1)\) in [20] were as small as the \(o(1)\) in [19], there would not be much benefit in \(1.901\ldots +o(1)\) compared to \(1.922\ldots +o(1)\). For example, \((2^{50})^{1.922}\approx 2^{96}\) while \((2^{50})^{1.901}\approx 2^{95}\).
The change from \(1.901\ldots +o(1)\) to \(1.638\ldots +o(1)\) is much larger, but it comes at the cost of massive memory consumption. Specifically, [20] requires space \(L^{1.638\ldots +o(1)}\), while [19] uses space just \(L^{0.961\ldots +o(1)}\). This is not visible in the RAM metric but is obviously a huge problem in reality, and it becomes increasingly severe as computations grow larger. As a concrete illustration of the real-world costs of storage and computation, paying for \(2^{70}\) bytes of slow storage (about \(30\cdot 10^9\) USD in hard drives) is much more troublesome than paying for \(2^{80}\) floating-point multiplications (about \(0.02\cdot 10^9\) USD in GPUs plus \(0.005\cdot 10^9\) USD for a year of electricity).
At the time there was already more than a decade of literature showing how to analyze algorithm asymptotics in more realistic models of computation that account for memory consumption, communication, etc.; see, e.g., [18]. Bernstein in [7] analyzed the circuit performance of NFS, concluding that an optimized circuit of area \(L^{0.790\ldots +o(1)}\) would factor \(N\) in time \(L^{1.18\ldots +o(1)}\), for price-performance ratio \(L^{1.976\ldots +o(1)}\). [7] did not analyze the factorization factory but did analyze multiple number fields, concluding that they did not reduce \(AT\) cost. The gap between the RAM exponent \(1.901\ldots +o(1)\) from [20] and the \(AT\) exponent \(1.976\ldots +o(1)\) from [7] is explained primarily by communication overhead inside linear algebra, somewhat moderated by parameter choices that reduce the cost of linear algebra at the expense of relation collection.
We pointed out in [14] that the factorization factory does not reduce \(AT\) cost. In Sect. 2 we review the reason for this and explain how batch NFS works around it. We also presented in [14] a superpolynomial improvement to the factorization factory in the RAM metric, by eliminating ECM in favor of batch trial division, but this is not useful in the \(AT\) metric.
2 Exponents
This section reviews NFS and then explains how to drastically reduce the \(AT\) cost of NFS through batching. The resulting cost exponent, \(1.704\ldots \) in Table 1.4, is new. All costs in this section are expressed as \(L^{e+o(1)}\) for various exponents \(e\). Section 3 looks more closely at the \(L^{o(1)}\) factor.
2.1 QS: the Quadratic sieve (1982). As a warmup for NFS we briefly review the general idea of combining congruences, using QS as an example.
QS writes down a large collection of congruences modulo the target integer \(N\) and tries to find a nontrivial subcollection whose product is a congruence of squares. One can then reasonably hope that the difference of square roots has a nontrivial factor in common with \(N\).
Specifically, QS computes \(s\approx \sqrt{N}\) and writes down the congruences \(s^2\equiv s^2-N\), \((s+1)^2\equiv (s+1)^2-N\), etc. The left side of each congruence is already a square. The main problem is to find a nontrivial set of integers \(a\) such that the product of \((s+a)^2-N\) is a square.
If \((s+a)^2-N\) is divisible by a very large prime then it is highly unlikely to participate in a square: the prime would have to appear a second time. QS therefore focuses on smooth congruences: congruences where \((s+a)^2-N\) factors completely into small primes. Applying linear algebra modulo 2 to the matrix of exponents in these factorizations is guaranteed to find nonempty subsets of the congruences with square product once the number of smooth congruences exceeds the number of small primes.
The integers \(a\) such that \((s+a)^2-N\) is divisible by a prime \(p\) form a small number of arithmetic progressions modulo \(p\). "Sieving" means jumping through these arithmetic progressions to mark divisibility, the same way that the sieve of Eratosthenes jumps through arithmetic progressions to mark non-primality.
2.2 NFS: the number-field sieve (1993). NFS applies the same idea, but instead of congruences modulo \(N\) it uses congruences modulo a related algebraic number \(m-\alpha \). This algebraic number is chosen to have norm \(N\) (divided by a certain denominator shown below), and one can reasonably hope to obtain a factorization of \(N\) by obtaining a random factorization of this algebraic number.
Specifically, NFS chooses a positive integer \(m\), and writes \(N\) as a polynomial in radix \(m\): specifically, \(N=f(m)\) where \(f\) is a degree-\(d\) polynomial with coefficients \(f_d,f_{d-1},\ldots ,f_0\in \mathord {\left\{ {0,1,\ldots ,m-1}\right\} }\). NFS then takes \(\alpha \) as a root of \(f\). The norm of \(a-b\alpha \) is then \(f_da^d+f_{d-1}a^{d-1}b+\cdots +f_0b^d\) (divided by \(f_d\)), and in particular the norm of \(m-\alpha \) is \(N\) (again divided by \(f_d\)).
The range of pairs \((a,b)\) searched for smooth congruences is the set of integer pairs in the rectangle \([-H,H]\times [1,H]\). Here \(H\) is chosen so that there will be enough smooth congruences to produce squares at the end of the algorithm. Standard heuristics state that \(a-bm\) has smoothness probability \(L^{-\mu /(3\gamma )+o(1)}\) if \(a\) and \(b\) are on much smaller scales than \(m\); in particular, if \(H\in L^{\theta +o(1)}\) for some positive real number \(\theta \) then the number of congruences with \(a-bm\) smooth is \(L^{\phi +o(1)}\) with \(\phi =2\theta -\mu /(3\gamma )\). Standard heuristics also state the simultaneous smoothness probability of \(a-bm\) and \(a-b\alpha \), implying that to obtain enough smooth congruences one can take \(H\in L^{\theta +o(1)}\) with \(\theta =(3\mu \gamma ^2+2\mu ^2)/(6\mu \gamma -1)\) and \(\phi =(18\mu \gamma ^3+6\mu ^2\gamma +\mu )/(18\mu \gamma ^2-3\gamma )\). See, e.g., [19]. We henceforth assume these formulas for \(\theta \) and \(\phi \) in terms of \(\mu \) and \(\gamma \).
2.3 RAM cost analysis (1993). Sieving for \(y\)-smoothness of \(H^{2+o(1)}\) polynomial values uses \(H^{2+o(1)}\) operations, provided that \(y\) is bounded by \(H^{2+o(1)}\). The point here is that the pairs \((a,b)\) with congruences divisible by \(p\) form a small number of shifted lattices of determinant \(p\), usually with basis vectors of length \(O(\sqrt{p})\), making it easy to find all the lattice points inside the rectangle \([-H,H]\times [1,H]\). The number of operations is thus essentially the number of points marked, and each point is marked just \(\sum _{p\le y} 1/p\approx \log \log y\) times.
Sparse techniques for linear algebra involve \(y^{1+o(1)}\) matrix-vector multiplications, each involving \(y^{1+o(1)}\) operations, for a total of \(y^{2+o(1)}\) operations. Other subroutines in NFS take negligible time, so the overall RAM cost of NFS is \(L^{\mathrm{max }\mathopen {}\mathord {\left\{ {2\theta ,2\gamma }\right\} }+o(1)}\).
It is not difficult to see that the exponent \(\mathrm{max }\mathopen {}\mathord {\left\{ {2\theta ,2\gamma }\right\} }\) achieves its minimum value \((64/9)^{1/3}=1.922\ldots \) with \(\mu =(1/3)^{1/3}=0.693\ldots \) and \(\theta =\gamma =(8/9)^{1/3}=0.961\ldots \). This exponent \(1.922\ldots \) is the NFS exponent from [19], and as mentioned earlier is the most frequently quoted NFS exponent. We do not review the multiple-number-fields improvement to \(1.901\ldots \) from [20]; as far as we know, multiple number fields do not improve any of the exponents analyzed below.
2.4 \(\boldsymbol{AT}\) cost analysis (2001). In the \(AT\) metric there is an important obstacle to cost \(H^{2+o(1)}\) for sieving: namely, communicating across area \(H^{2+o(1)}\) takes time at least \(H^{1+o(1)}\). One can efficiently split the sieving problem into \(H^{2+o(1)}/y^{1+o(1)}\) tasks, running one task after another on a smaller array of size \(y^{1+o(1)}\), but communicating across this array still takes time at least \(y^{0.5+o(1)}\), so \(AT\) is at least \(H^{2+o(1)}y^{0.5+o(1)}\).
Fortunately, there is a much more efficient alternative to sieving: ECM, explained in Appendix A of the full version of this paper online. What matters in this section is that ECM tests \(y\)-smoothness in time \(y^{o(1)}\) on a circuit of area \(y^{o(1)}\). A parallel array of ECM units, each handling a separate number, tests \(y\)-smoothness of \(H^{2+o(1)}\) polynomial values in time \(H^{2+o(1)}/y^{1+o(1)}\) on a circuit of area \(y^{1+o(1)}\), achieving \(AT=H^{2+o(1)}\).
Unfortunately, the same obstacle shows up again for linear algebra, and this time there is no efficient alternative. Multiplying a sparse matrix by a vector requires time \(y^{0.5+o(1)}\) on a circuit of area \(y^{1+o(1)}\), and must be repeated \(y^{1+o(1)}\) times. The overall \(AT\) cost of NFS is \(L^{\mathrm{max }\mathopen {}\mathord {\left\{ {2\theta ,2.5\gamma }\right\} }+o(1)}\).
The exponent \(\mathrm{max }\mathopen {}\mathord {\left\{ {2\theta ,2.5\gamma }\right\} }\) achieves its minimum value \(1.976\ldots \) with \(\mu =0.702\ldots \), \(\gamma =0.790\ldots \), and \(\theta =0.988\ldots \). This exponent \(1.976\ldots \) is the NFS exponent from [7]. Notice that \(\gamma \) is much smaller here than it was in the RAM optimization: \(y\) has been reduced to keep the cost of linear algebra under control, but this also forced \(\theta \) to increase.
2.5 The factorization factory (1993). Coppersmith in [20] precomputes "tables which will be useful for factoring any integers in a large range ... after the precomputation, an individual integer can be factored in time \(L[1/3,1.639]\)", i.e., \(L^{{\approx }1.639+o(1)}\).
Coppersmith's table is simply the set of \((a,b)\) such that \(a-bm\) is smooth. One reuses \(m\), and thus this table, for any integer \(N\) between (e.g.) \(m^d\) and \(m^{d+1}\).
Coppersmith's method to factor "an individual integer" is to test smoothness of \(a-b\alpha \) for each \((a,b)\) in the table. At this point Coppersmith has found the same smooth congruences as conventional NFS, and continues with linear algebra in the usual way.
Coppersmith uses ECM to test smoothness. The problem with sieving here is not efficiency, as in the (subsequent) paper [7], but functionality: sieving can handle polynomial values only at regularly spaced inputs, and the pairs \((a,b)\) in this table are not regularly spaced.
Recall that the size of this table is \(L^{\phi +o(1)}\) with \(\phi =2\theta -\mu /(3\gamma )\). ECM uses \(L^{o(1)}\) operations per number, for a total smoothness cost of \(L^{\phi +o(1)}\), asymptotically a clear improvement over the \(L^{2\theta +o(1)}\) for conventional NFS.
The overall RAM cost of the factorization factory is \(L^{\mathrm{max }\mathopen {}\mathord {\left\{ {\phi ,2\gamma }\right\} }+o(1)}\). The exponent achieves its minimum value \(1.638\ldots \) with \(\mu =0.905\ldots \), \(\gamma =0.819\ldots \), \(\theta =1.003\ldots \), and \(\phi =1.638\ldots \). This is the exponent from [20].
The \(AT\) metric tells a completely different story, as we pointed out in [14]. The area required for the table is \(L^{\phi +o(1)}\). This area is easy to reuse for very fast parallel smoothness detection, finishing in time \(L^{o(1)}\). Unfortunately, collecting the smooth results then takes time \(L^{0.5\phi +o(1)}\), for an \(AT\) cost of at least \(L^{\mathrm{max }\mathopen {}\mathord {\left\{ {1.5\phi ,2.5\gamma }\right\} }+o(1)}\), never mind the problem of matching the table area with the linear-algebra area. The minimum exponent here is above \(2.4\).
2.6 Batch NFS (new). We drastically reduce \(AT\) cost by sharing work across many \(N\)'s in a different way: we process a batch of \(N\)'s in parallel, rather than performing precomputation to be used for one \(N\) at a time. We dynamically enumerate the pairs \((a,b)\) with \(a-bm\) smooth, distribute each pair across all the \(N\)'s in the batch, and remove each pair as soon as possible, rather than storing a complete table of the pairs. To avoid excessive communication costs we completely reorganize data in the middle of the computation: at the beginning each \(N\) is repeated many times to bring \(N\) close to the pairs \((a,b)\), while at the end the pairs \((a,b)\) relevant to each \(N\) are moved much closer together. The rest of this subsection presents the details of the algorithm.
Consider as input a batch of \(L^{\beta +o(1)}\) simultaneous targets \(N\) within the large range described above. We require \(\beta \le \mathrm{min }\mathopen {}\mathord {\left\{ {2\phi -2\gamma ,4\theta -2\phi }\right\} }\); if there are more targets available at once then we actually process those targets in batches of size \(L^{\mathrm{min }\mathopen {}\mathord {\left\{ {2\phi -2\gamma ,4\theta -2\phi }\right\} }+o(1)}\), storing no data between runs.
Consider a square mesh of \(L^{\beta +o(1)}\) small parallel processors. This mesh is large enough to store all of the targets \(N\). Use each processor in parallel to test smoothness of \(a-bm\) for \(L^{2\theta -\phi -0.5\beta +o(1)}\) pairs \((a,b)\) using ECM; by hypothesis \(2\theta -\phi -0.5\beta \ge 0\). The total number of pairs here is \(L^{2\theta -\phi +0.5\beta +o(1)}\). Each smoothness test takes time \(L^{o(1)}\). Overall the mesh takes time \(L^{2\theta -\phi -0.5\beta +o(1)}\) and produces a total of \(L^{0.5\beta +o(1)}\) pairs \((a,b)\) with \(a-bm\) smooth, i.e., only \(L^{o(1)}\) pairs for each column of the mesh. See Fig. 2.7.
Move these pairs to the top row of the mesh (spreading them evenly across that row) by a standard sorting algorithm, say the Schnorr–Shamir algorithm from [50], taking time \(L^{0.5\beta +o(1)}\). Then broadcast each pair to its entire column, taking time \(L^{0.5\beta +o(1)}\). Actually, it will suffice for each pair to appear once somewhere in the first two rows, once somewhere in the next two rows, etc.
Observe that each pair has now visited each position in the mesh. When a pair \((a,b)\) visits a mesh position holding a target \(N\), use ECM to check whether \(a-b\alpha \) is smooth, taking time \(L^{o(1)}\). The total time to check all \(L^{0.5\beta +o(1)}\) pairs against all \(L^{\beta +o(1)}\) targets is just \(L^{0.5\beta +o(1)}\), plus the time \(L^{2\theta -\phi -0.5\beta +o(1)}\) to generate the pairs in the first place. See Fig. 2.8.
Repeat this entire procedure \(L^{\phi -\gamma -0.5\beta +o(1)}\) times; by hypothesis \(\phi -\gamma -0.5\beta \ge 0\). This covers a total of \(L^{2\theta -\gamma +o(1)}\) pairs \((a,b)\), of which \(L^{\phi -\gamma +o(1)}\) have \(a-bm\) smooth, so for each \(N\) there are \(L^{o(1)}\) pairs \((a,b)\) for which \(a-bm\) and \(a-b\alpha \) are both smooth. The total number of smooth congruences found this way across all \(N\) is \(L^{\beta +o(1)}\). Store each smooth congruence as \((N,a,b)\); all of these together fit into a mesh of area \(L^{\beta +o(1)}\). The time spent is \(L^{\mathrm{max }\mathopen {}\mathord {\left\{ {\phi -\gamma ,2\theta -\gamma -\beta }\right\} }+o(1)}\).
We are not done yet: we still need to perform linear algebra for each \(N\). To keep the communication costs of linear algebra under control we pack the linear algebra for each \(N\) into the smallest possible area. Allocate a separate square of area \(L^{\gamma +o(1)}\) to each \(N\), and route each smooth congruence \((N,a,b)\) in parallel to the corresponding square; this is another standard sorting step, taking total time \(L^{0.5\beta +0.5\gamma +o(1)}\) for all \(L^{\beta +\gamma +o(1)}\) smooth congruences. Finally, perform linear algebra separately in each square, and complete the factorization of each \(N\) as usual. This takes time \(L^{1.5\gamma +o(1)}\). See Fig. 2.10.
The overall time exponent is \(\mathrm{max }\mathopen {}\mathord {\left\{ {\phi -\gamma ,2\theta -\gamma -\beta ,0.5\beta +0.5\gamma ,1.5\gamma }\right\} }\), and the area exponent is \(\beta +\gamma \). The final price-performance ratio, \(AT\) per integer factored, has exponent \(\mathrm{max }\mathopen {}\mathord {\left\{ {\phi ,2\theta -\beta ,0.5\beta +1.5\gamma ,2.5\gamma }\right\} }\).
2.11 Comparison and numerical parameter optimization. Bernstein's \(AT\) exponent from [7] was \(\mathrm{max }\mathopen {}\mathord {\left\{ {2\theta ,2.5\gamma }\right\} }\). Batch NFS replaces \(2\theta \) with \(2\theta -\beta \), allowing \(\gamma \) to be correspondingly reduced, at least until \(\beta \) becomes large enough for \(2.5\gamma \) to cross below \(\phi \). In principle one should also watch for \(2.5\gamma \) to cross below \(0.5\beta +1.5\gamma \), but Table 2.12 shows that \(\phi \) is more important.
Of course, even if we ignore the cost of finding the smooth \(a-bm\) (the term \(2\theta -\beta \)), our \(AT\) exponent is not as small as Coppersmith's RAM exponent \(\mathrm{max }\mathopen {}\mathord {\left\{ {\phi ,2\gamma }\right\} }\) from [20]. We have an extra \(0.5\beta +1.5\gamma \) term, reflecting the cost of communicating smooth congruences across a batch, and, more importantly, \(2.5\gamma \) instead of \(2\gamma \), reflecting the communication cost of linear algebra.
Table 2.12 shows the smallest exponents that we obtained for various \(\beta \), in each case from a brief search through 2500000000 pairs \((\mu ,\gamma )\). The exponent of the price-performance ratio for batch NFS drops below Bernstein's \(1.976\ldots \) as soon as \(\beta \) increases past \(0\), and reaches a minimum of \(1.704\ldots \) as the batch size increases. (The minimum is actually very slightly below \(1.704\), but our table does not include enough precision to show this.) Finding all \((a,b)\) with \(a-bm\) smooth is still a slight bottleneck for \(\beta =0.4\) but disappears for \(\beta =0.5\). When there are more inputs we partition them into batches of size \(L^{0.5+o(1)}\), preserving exponent \(1.704\ldots \) for the price-performance ratio.
Cost exponents for batch NFS in the \(AT\) metric. The batch size is \(L^{\beta +o(1)}\). The \(AT\) cost is \(L^{e+o(1)}\). The parameter \(m\) is chosen as \(\exp ((\mu +o(1))(\log N)^{2/3}(\log \log N)^{1/3})\). The prime bound \(y\) is chosen as \(L^{\gamma +o(1)}\). The \((a,b)\) bound \(H\) is chosen as \(L^{\theta +o(1)}\). The number of \(a-b\alpha \) smoothness tests is \(L^{\phi +o(1)}\) per target. The number of \(a-bm\) somothness tests is \(L^{2\theta -\beta +o(1)}\) per target. The \(AT\) cost of routing is \(L^{0.5\beta +1.5\gamma +o(1)}\) per target. The \(AT\) cost of linear algebra is \(L^{2.5\gamma +o(1)}\) per target. All operations take place on a circuit of size \(L^{\beta +\gamma +o(1)}\).
\(m\) size
\(a-b\alpha \)
\(\beta \)
\(\mu \)
\(\gamma \)
\(\theta \)
\(\phi \)
\(2\theta -\beta \)
\(0.5\beta +1.5\gamma \)
\(2.5\gamma \)
3 Early-abort ECM
Section 2 used ECM as a low-area smoothness test for auxiliary integers \(c=f_d a^d+\cdots +f_0 b^d\). Each curve in ECM catches a fraction of the primes \(p\le y\) dividing \(c\), and many curves in sequence catch essentially all of the primes \(p\le y\).
This section analyzes a much faster smoothness-detection method, "early-abort ECM". Not all smooth numbers are detected by early-abort ECM, but new heuristics introduced in this section imply that this loss is much smaller than the speedup factor. The overall improvement grows as a superpolynomial function of \(\log y\), and therefore grows as a superpolynomial function of the NFS input size.
We emphasize again that this paper's analyses are asymptotic. We do not claim that early-abort ECM is better than ECM for any particular value of \(y\).
The rest of this section uses the word "time" to count simple arithmetic operations, such as multiplication and division, on integers with \(O(\lg c)\) bits. Each of these operations actually takes time \((\lg c)^{1+o(1)}\), but this extra factor is absorbed into other \(o(1)\) terms when \(c\) is bounded by the usual functions of \(y\).
3.1 Early-abort trial division. Early aborts predate ECM. They became popular in the 1970s as a component of CFRAC [43], a subexponential-time factorization method that, like batch NFS, generates many "random" numbers that need to be tested for smoothness.
The simplest form of early aborts is single-early-abort trial division. Trial division simply checks divisibility of \(c\) by each prime \(p\le y\), taking time \(y^{1+o(1)}\). Single-early-abort trial division first checks divisibility of \(c\) by each prime \(p\le y^{1/2}\); then throws \(c\) away (this is the early abort) if the unfactored part of \(c\) is too large; and then, if \(c\) has survived the early abort, checks divisibility of \(c\) by each prime \(p\le y\).
The definition of "too large" is chosen so that \(1/y^{1/2+o(1)}\) of all inputs survive the abort, balancing the cost of the stages before and after the abort. In other words, single-early-abort trial division checks divisibility of each input by each prime \(p\le \sqrt{y}\); keeps the smallest \(1/y^{1/2+o(1)}\) of all inputs; and, for each of those inputs, checks divisibility by each prime \(p\le y\).
More generally, \((k-1)\)-early-abort trial division removes each prime \(p\le y^{1/k}\) from each input (by dividing by factors found); reduces the number of inputs by a factor of \(y^{1/k}\), keeping the smallest inputs; removes each prime \(p\le y^{2/k}\) from each remaining input; reduces the number of inputs by another factor of \(y^{1/k}\), keeping the smallest inputs; and so on through \(y^{k/k}=y\).
The time per input for \((k-1)\)-early-abort trial division is only \(y^{1/k+o(1)}\), saving a factor \(y^{1-1/k+o(1)}\), if \(k\) is limited to a slowly growing function of \(y\). The method does not detect all smooth numbers, but Pomerance's analysis in [45, Sect. 4] shows that the loss factor is only \(y^{(1-1/k)/2+o(1)}\), i.e., that the method detects \(1\) out of every \(y^{(1-1/k)/2+o(1)}\) smooth numbers. The overall improvement factor in price-performance ratio is \(y^{(1-1/k)/2+o(1)}\); if \(k\) is chosen so that \(k\rightarrow \infty \) as \(y\rightarrow \infty \) then the improvement factor is \(y^{1/2+o(1)}\).
3.2 Early aborts in more generality. One can replace trial division with any method, or combination of methods, of checking for primes \(\le y^{1/k}\), primes \(\le y^{2/k}\), etc.
In particular, Pomerance considered an early-abort version of Pollard's rho method. The original method takes time \(y^{1/2+o(1)}\) to find all primes \(p\le y\). Early-abort rho takes time only \(y^{1/(2k)+o(1)}\), and Pomerance's analysis shows that it has a loss factor of only \(y^{(1-1/k)/4+o(1)}\).
Pomerance actually considered a different method by Pollard and Strassen. The Pollard–Strassen method takes essentially the same amount of time as Pollard's rho method, and has the advantage of a proof of speed without any conjectures, but has the disadvantage of using much more memory.
Pomerance's paper was published in 1982, so of course it did not analyze the elliptic-curve method. After seeing early aborts improve trial division from \(y\) to \(y^{1/2}\), and improve Pollard's rho method from \(y^{1/2}\) to \(y^{1/4}\), one might guess that early aborts improve ECM from \(\exp (\sqrt{(2+o(1)){\log y\log \log y}})\) to \(\exp ((1/2)\sqrt{(2+o(1)){\log y\log \log y}})\), but our heuristics do not agree with this guess.
3.3 Performance of early aborts. Recall that ECM takes time \(T(y)^{1+o(1)}\) to find primes \(p\le y\), where \(T(y)=\exp (\sqrt{2\log y\log \log y})\). We actually consider, in much more generality, any factorization method \(M\) taking time \(T(y)^{1+o(1)}\) to find primes \(p\le y\), where \(T\) is any sufficiently smooth function.
3.4 Understanding the heuristics. Let \(y\) and \(u\) be real numbers larger than \(1\), define \(x=y^u\), and define \(S_0=\mathord {\left\{ {1,2,\ldots ,\mathord {\left\lfloor {x}\right\rfloor }}\right\} }\). Define \(\varPsi (x,y)\) as the number of \(y\)-smooth integers in \(S_0\). Then \(\varPsi (x,y)\) is approximately \(x/u^u\). See [45, Theorem 2.1] for a precise statement. The same approximation is still valid for \(\varPsi (x,y,z)\), the number of \(y\)-smooth integers in \(S_0\) having no prime factor \({\le z}\), assuming that \(z<y^{1-1/{\log u}}\); see [45, Theorem 2.2].
Consider any vector \((s_1,s_2,\ldots ,s_k)\) such that each \(s_i\) is a \(y_i\)-smooth positive integer \({\le }x_i\) having no prime factors \({\le }y_{i-1}\). For any such \((s_1,s_2,\ldots ,s_k)\), the product \(c=s_1s_2\cdots s_k\) is a positive integer bounded by \(x_1x_2\cdots x_k=x\), so \(c\in S_0\). Dividing \(c\) by its \(y_1\)-smooth part produces \(s_2\cdots s_k\le x/x_1\), so \(c\in S_1\). Similarly \(c\in S_2\) and so on through \(c\in S_k\).
The map from \((s_1,s_2,\ldots ,s_k)\) to \(s_1s_2\cdots s_k\in S_k\) is injective: the \(y_1\)-smooth part of \(s_1s_2\cdots s_k\) is exactly \(s_1\), the \(y_2\)-smooth part is exactly \(s_1s_2\), etc. Hence \(\#S_k\) is at least the number of such vectors \((s_1,s_2,\ldots ,s_k)\), which is exactly \(\varPsi (x_1,y_1,y_0) \varPsi (x_2,y_2,y_1) \varPsi (x_3,y_3,y_2) \cdots \varPsi (x_k,y_k,y_{k-1})\). Pomerance's early-abort analysis in [45] says, in some cases, that \(\#S_k\) is not much larger than this. We heuristically assume that this is true in more generality.
The approximation \(\varPsi (x_i,y_i,y_{i-1})\approx x_i/u_i^{u_i}\), where \(u_i=(\log x_i)/\log y_i\), now implies that \(\#S_k\) is approximately \(x/(u_1^{u_1}\cdots u_k^{u_k})\). More generally, \(\#S_i\) is approximately \(x/(u_1^{u_1}\cdots u_i^{u_i})\).
Write \(T_i\) for the cost of finding the \(y_i\)-smooth part of an integer. The early-abort factorization method, applied to a uniform random element of \(S_0\), always takes time \(T_1\) to find primes \({\le }y_1\); with probability \(\#S_1/\#S_0\approx 1/u_1^{u_1}\) takes additional time \(T_2\) to find primes \({\le }y_2\); with probability \(\#S_2/\#S_0\approx 1/(u_1^{u_1}u_2^{u_2})\) takes additional time \(T_3\) to find primes \({\le }y_3\); and so on. With probability \(\#S_k/\#S_0\approx 1/(u_1^{u_1}\cdots u_k^{u_k})\) an integer survives all aborts and is \(y\)-smooth.
Balancing the time for the early-abort stages, i.e., ensuring that each stage takes time approximately \(T_1\), requires choosing \(x_1\) (depending on \(y_1\)) so that \(u_1^{u_1}\approx T_2/T_1\), choosing \(x_2\) (depending on \(y_2\)) so that \(u_2^{u_2}\approx T_3/T_2\), and so on through choosing \(x_{k-1}\) (depending on \(y_{k-1}\)) so that \(u_{k-1}^{u_{k-1}}\approx T_k/T_{k-1}\). Then \(x_k\) is determined as \(x/(x_1\cdots x_{k-1})\), and \(u_k\) is determined as \((\log x_k)/\log y_k =u-(\log x_1\cdots x_{k-1})/\log y =u-(\theta _1 u_1+\theta _2 u_2+\cdots +\theta _{k-1} u_{k-1}) \) where \(\theta _i=(\log y_i)/\log y\).
We see two obstacles to proving the formula \((T_1T_2\cdots T_k)^{1/k}\) for early-abort ECM. First, the assumption \(u_i\in u^{1+o(1)}\) is correct for exponential-time smoothness tests for standard ranges of \(x\) and \(y\); but \(u_i\in u^{0.5+o(1)}\) for ECM, except for \(i=k\). Second, the error factor \(u^{o(u)}\) in the standard \(u^u\) approximation is larger than the entire ECM running time. Despite these caveats we conjecture that the heuristics apply beyond the case of exponential-time smoothness tests, and in particular apply to early-abort ECM.
Even when smoothness theorems are available, one should not overstate the extent to which they constitute rigorous analyses of NFS. There is no proof that NFS congruences have similar smoothness probability to uniform random integers; this is one of the NFS heuristics. There is no proof that ECM finds all small primes at similar speed; this is another heuristic. As mentioned earlier, Pomerance's analysis in [45] actually uses the provable Pollard–Strassen smoothness-detection method, and Bernstein's batch trial-division method [8] is proven to run in polynomial time per input; but both of these methods perform poorly in the \(AT\) metric. Similarly, Pomerance proved in [45] that Dixon's random squares have similar smoothness probability to uniform random integers; but Dixon's method is much slower than NFS, and proving something similar about NFS is an open problem.
3.5 Impact of early aborts on smoothness probabilities. Because early-abort ECM does not find all smooth values, it forces batch NFS to consider more pairs \((a,b)\), and therefore slightly larger pairs \((a,b)\). This increase means that the auxiliary integers \(c\) are larger and less likely to be smooth. We conclude by showing that this effect does not eliminate the (heuristic) asymptotic gain produced by early aborts.
Recall that the smoothness probability of \(c\) is heuristically \(1/v^v\), where \(v\) is the ratio of the number of bits in \((|f_d|+\cdots +|f_0|)H^d\) and the number of bits in \(y\). The derivative of \(v\) with respect to \(\log H\) is \(d/\log y\), so the derivative of \(\log (v^v)\) with respect to \(\log H\) is \(d(1+\log v)/\log y\in 1/(3\gamma \mu )+o(1)\); here we have used the asymptotics \(d\in (1/\mu +o(1))(\log N)^{1/3}(\log \log N)^{-1/3}\), \(\log y\in (\gamma +o(1))(\log N)^{1/3}(\log \log N)^{2/3}\), and \(\log v\in (1/3+o(1))\log \log N\).
Write \(\delta =(2/3)/(2-1/(3\gamma \mu ))\). Multiplying \(H\) by a factor \(T^{\delta +o(1)}\) means multiplying the number of pairs \((a,b)\) by a factor \(T^{2\delta +o(1)}\) and thus multiplying the number of smoothness tests by a factor \(T^{2\delta +o(1)}\). Meanwhile it multiplies \(v^v\) by a factor \(T^{\delta /(3\gamma \mu )+o(1)}\), and thus multiplies the final number of smooth congruences by a factor \(T^{(2-1/(3\gamma \mu ))\delta +o(1)}=T^{2/3+o(1)}\). Our heuristics state that switching from ECM to early-abort ECM reduces the number of smooth congruences found by a factor \(T^{2/3+o(1)}\), producing just enough smooth congruences for a successful factorization, while decreasing the cost of each smoothness test by a factor \(T^{1+o(1)}\). The overall speedup factor is \(T^{1-2\delta +o(1)}\).
For example, [7] took \(\gamma \approx 0.790420\) and \(\mu \approx 0.702860\), so the speedup factor is \(T^{0.047\ldots +o(1)}\). As another example, batch NFS with \(\beta =0.5\) takes \(\gamma \approx 0.681600\) and \(\mu \approx 0.921150\), so the speedup factor is \(T^{0.092\ldots +o(1)}\).
- [4]Bai, S., Bouvier, C., Filbois, A., Gaudry, P., Imbert, L., Kruppa, A., Morain, F., Thomé, E., Zimmermann, P.: CADO-NFS—Crible Algébrique: Distribution, Optimisation—Number Field Sieve (2013). http://cado-nfs.gforge.inria.fr/. Citations in this document: §1
- [6]Barker, E., Barker, W., Burr, W., Polk, W., Smid, M.: Recommendation for key management—part 1: general (revision 3) (2012). http://csrc.nist.gov/publications/nistpubs/800-57/sp800-57_part1_rev3_general.pdf. Citations in this document: §1.2
- [7]Bernstein, D.J.: Circuits for integer factorization: a proposal (2001). http://cr.yp.to/papers.html#nfscircuit. Citations in this document: §1.1, §1.3, §1.3, §1.3, §1.3, §2.4, §2.5, §2.11, §3.5
- [8]Bernstein, D.J.: How to find small factors of integers (2002). http://cr.yp.to/papers.html#sf. Citations in this document: §3.4
- [10]Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: ECM using Edwards curves. Math. Comput. 82, 1139–1179 (2013). Citations in this document: §AGoogle Scholar
- [11]Bernstein, D.J., Chen, H.-C., Chen, M.-S., Cheng, C.-M., Hsiao, C.-H., Lange, T., Lin, Z.-C. , Yang, B.-Y.: The billion-mulmod-per-second PC. In: Workshop Record of SHARCS'09: Special-Purpose Hardware for Attacking Cryptographic Systems, pp. 131–144 (2009). http://www.hyperelliptic.org/tanja/SHARCS/record2.pdf. Citations in this document: §1.2
- [12]Bernstein, D.J., Chen, T.-R., Cheng, C.-M., Lange, T., Yang, B.-Y.: ECM on graphics cards. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 483–501. Springer, Heidelberg (2009). Citations in this document: §1.2CrossRefGoogle Scholar
- [14]Bernstein, D.J., Lange, T.: Non-uniform cracks in the concrete: the power of free precomputation. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part II. LNCS, vol. 8270, pp. 321–340. Springer, Heidelberg (2013). Citations in this document: §1.2, §1.3, §1.3, §2.5CrossRefGoogle Scholar
- [15]Bilardi, G., Preparata, F.P.: Horizons of parallel computation. J. Parallel Distrib. Comput. 27, 172–182 (1995). Citations in this document: §1.1CrossRefzbMATHGoogle Scholar
- [17]Bos, J.W., Kleinjung, T.: ECM at work. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 467–484. Springer, Heidelberg (2012). Citations in this document: §1.2CrossRefGoogle Scholar
- [18]Brent, R.P., Kung, H.T.: The area-time complexity of binary multiplication. J. ACM 28, 521–534 (1981). Citations in this document: §1.1, §1.3MathSciNetCrossRefzbMATHGoogle Scholar
- [19]Buhler, J.P., Lenstra Jr., H.W., Pomerance, C.: Factoring integers with the number field sieve. See [23], pp. 50–94 (1993). Citations in this document: §1.3, §1.3, §1.3, §1.3, §1.3, §1.3, §2.2, §2.3Google Scholar
- [20]Coppersmith, D.: Modifications to the number field sieve. J. Cryptol. 6, 169–180 (1993). Citations in this document: §1.3, §1.3, §1.3, §1.3, §1.3, §1.3, §1.3, §1.3, §2.3, §2.5, §2.5, §2.11MathSciNetCrossRefzbMATHGoogle Scholar
- [21]Crandall, R., Pomerance, C.: Prime numbers: A Computational Perspective. Springer, New York (2001). Citations in this document: §3CrossRefzbMATHGoogle Scholar
- [23]Franke, J., Kleinjung, T., Paar, C., Pelzl, J., Priplata, C., Stahlke, C.: SHARK: a realizable special hardware sieving device for factoring 1024-bit integers. In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 119–130. Springer, Heidelberg (2005). Citations in this document: §1, §1.1Google Scholar
- [24]Geiselmann, W., Shamir, A., Steinwandt, R., Tromer, E.: Scalable hardware for sparse systems of linear equations, with applications to integer factorization. In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 131–146. Springer, Heidelberg (2005). Citations in this document: §1, §1.1CrossRefGoogle Scholar
- [25]Heninger, N., Durumeric, Z., Wustrow, E., Halderman, J.A.: Mining your Ps and Qs: detection of widespread weak keys in network devices. In: USENIX Security Symposium (2012). Citations in this document: §1.1Google Scholar
- [29]Kleinjung, T.: On polynomial selection for the general number field sieve. Math. Comput. 75, 2037–2047 (2006). Citations in this document: §1MathSciNetCrossRefzbMATHGoogle Scholar
- [30]Kleinjung, T.: Polynomial selection. Slides presented at the CADO workshop, Nancy, France (2008). http://cado.gforge.inria.fr/workshop/slides/kleinjung.pdf. Citations in this document: §1
- [31]Kleinjung, T., Aoki, K., Franke, J., Lenstra, A.K., Thomé, E., Bos, J.W., Gaudry, P., Kruppa, A., Montgomery, P.L., Osvik, D.A., te Riele, H.J.J., Timofeev, A., Zimmermann, P.: Factorization of a 768-bit RSA modulus. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 333–350. Springer, Heidelberg (2010). Citations in this document: §1CrossRefGoogle Scholar
- [32]Kolkman, O.M., Mekking, M., Gieben, M.: RFC 6781: DNSSEC operational practices, version 2 (2012). http://tools.ietf.org/html/rfc6781. Citations in this document: §1
- [35]Lenstra, A.K., Hughes, J.P., Augier, M., Bos, J.W., Kleinjung, T., Wachter, C.: Public keys. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 626–642. Springer, Heidelberg (2012). Citations in this document: §1.1CrossRefGoogle Scholar
- [36]Lenstra, A.K., Lenstra Jr., H.W. (eds.): The Development of the Number Field Sieve. Lecture Notes in Mathematics, vol. 1554. Springer, Berlin (1993). Citations in this document: §1. See [19]zbMATHGoogle Scholar
- [37]Lenstra, A.K., Lenstra Jr., H.W., Manasse, M.S., Pollard, J.M.: The factorization of the ninth Fermat number. Math. Comput. 61, 319–349 (1993). Citations in this document: §1.3MathSciNetCrossRefzbMATHGoogle Scholar
- [38]Lenstra, A.K., Tromer, E., Shamir, A., Kortsmit, W., Dodson, B., Hughes, J., Leyland, P.: Factoring estimates for a 1024-bit RSA modulus. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 55–74. Springer, Heidelberg (2003). Citations in this document: §1CrossRefGoogle Scholar
- [40]Lenstra Jr., H.W., Tijdeman, R. (eds.): Computational Methods in Number Theory I. Mathematical Centre Tracts, vol. 154. Mathematisch Centrum, Amsterdam (1982). See [45]zbMATHGoogle Scholar
- [41]Lewis, E.: DNSSEC at TLDs, start of 4Q 2013 (2013). https://elists.isoc.org/pipermail/dnssec-coord/2013-October/000172.html. Citations in this document: §1
- [43]Morrison, M.A., Brillhart, J.: A method of factoring and the factorization of \(F_7\). Math. Comput. 29, 183–205 (1975). Citations in this document: §3.1MathSciNetzbMATHGoogle Scholar
- [45]Pomerance, C.: Analysis and comparison of some integer factoring algorithms. In: [40], pp. 89–139 (1982). http://cr.yp.to/bib/1982/pomerance.html. Citations in this document: §3.1, §3.4, §3.4, §3.4, §3.4, §3.4
- [50]Schnorr, C.P., Shamir, A.: An optimal sorting algorithm for mesh-connected computers. In: STOC 1986, pp. 255–261 (1986). Citations in this document: §1.1, §2.6Google Scholar
- [51]Shamir, A., Tromer, E.: Factoring large numbers with the TWIRL device. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 1–26. Springer, Heidelberg (2003). Citations in this document: §1, §1.1, §1.2CrossRefGoogle Scholar
- [53]Thompson, C.D., Kung, H.T.: Sorting on a mesh-connected parallel computer. Commun. ACM 20, 263–271 (1977). Citations in this document: §1.1MathSciNetCrossRefzbMATHGoogle Scholar
- [54]van Oorschot, P.C., Wiener, M.: Parallel collision search with cryptanalytic applications. J. Cryptol. 12, 1–28 (1999). Citations in this document: §1.1MathSciNetCrossRefzbMATHGoogle Scholar
- [56]Wiener, M.J.: The full cost of cryptanalytic attacks. J. Cryptol. 17, 105–124 (2004). Citations in this document: §1.1MathSciNetCrossRefzbMATHGoogle Scholar


text:
DiRT Rally 2.0 Gets New Gameplay Video
Deep Silver and Codemasters have released a new trailer for DiRT Rally 2.0 that shows off the game's rally action.
The trailer, called "World RX In Motion," takes a closer look at the title's FIA World Rallycross Championship events. Eight tracks from the Championship will be included at launch, including Mettet, Silverstone and Circuit de Barcelona – Catalunya. Four different classes of rallycross cars will also be available at launch in DiRT Rally 2.0, including RX2, RX Super 1600s, and RX Crosskarts.
You can view the trailer below:
World RX in Motion | DiRT Rally 2.0 [US]
According to Paul Bellamy, Senior Vice President of IMG Motorsports:
Jonathan Bunney, SVP of Publishing at Codemasters added:
The game will come out for the PlayStation 4, Xbox One, and PC on February 26.
in News
Rockstar Games announced today that the Red Dead Online Beta will see 25% off all available weapons at Fences this week
in News
Capcom's tale of swords, sorcery and revenge, Dragon's Dogma: Dark Arisen, has made its way to the Nintendo Switch
in News
SEGA announced today that Puyo Puyo Champions will make its way to the PlayStation 4, Xbox One, Nintendo Switch, and PC on May 7
in News
Ahead of its launch on April 25 for the Nintendo Switch, Image & Form has unveiled the release trailer for SteamWorld Quest

subset: commoncrawl


text:
Bear River Pines Fuel Reduction Project
- SCH Number
- 2016128291
- Lead Agency
- Forestry and Fire Protection, Department of (Cal Fire)
- Document Title
- Bear River Pines Fuel Reduction Project
- Document Type
- NOE - Notice of Exemption
- Received
- Document Description
- The Bear River Pines Fuel Reduction Project is a shaded fuel break that will include thinning from below to remove dead, diseased and suppressed trees. Thinning will be implemented through a combination of the following: mastication, handwork and pile burn, or handwork and chopping on a total of 100 acres. Burning will occur on the handwork acres and piles will be no larger than 8x8. This work focuses on reducing fire hazard, improving ingress/egress throughout the community and improving forest health.
- Contact Information
Elsa Hucks
Cal Fire
13760 Lincoln Way
Auburn, CA 95604
- Counties
- Nevada
- Township
- Range
- Section
- 9,10
- Base
Notice of Exemption
- Exempt Status
- Categorical Exemption
- Type, Section or Code
- Reasons for Exemption
- Field review by CAL FIRE staff confirmed that no exceptions apply which would preclude the use of a Notice of Exemption for this project. The department has concluded that no significant environmental impact would occur to aesthetics, agriculture and forestland/timberland, air quality, biological resources, cultural resources, geology and soils, greenhouse gas emissions, hazards and hazardous materials, hydrology and water quality, land use planning, mineral resources, noise ,population and housing, public services, recreation, transportation/traffic, or to utilities and service systems.


text:
Celebrate Easter with The Greens.
We have a weekend full of live music and kids activities to keep everyone 'hoppy'!
PLUS on Sunday, we earn our treats with some Easter Egg-tivities starting with special Easter face painting, a visit from a furry friend at midday a balloonist at 1pm and our petting zoo with lots of real bunnies to cuddle. We also have an Easter egg hunt for kids of all ages at 12.30pm plus so much more!
Come hop along.
Date: Friday 19th – Sunday 21st April 2019
Time: All Weekend
Cost: FREE!


text:
An improved two-machine flowshop scheduling with intermediate transportation
- 246 Downloads
- Citations
A two-machine flowshop scheduling problem with intermediate transportation is investigated in this paper, where jobs of varying sizes finished on the first machine need to be transported to the other machine for further processing. One service vehicle of a limited capacity is used for transportation between the two machines. The problem objective is to minimize the makespan, that is the finishing time of the last job on the second machine. Using a better bin-packing algorithm and balancing between two schedules, we present an \(\frac{11}{5}\)-approximation algorithm for the problem, which improves the previously best \(\frac{7}{3}\)-approximation algorithm by Gong and Tang.
KeywordsFlowshop scheduling Bin-packing Approximation algorithm Worst-case performance analysis
Dong is supported by the Zhejiang Provincial Natural Science Foundation Grants No. LY13A010015 and the Science Foundation of Zhejiang Sci-Tech University (ZSTU) Grants No. 13062171-Y; Hu is supported by National Natural Science Foundation of China Grants No. 11271324 and 11471286; Lin is supported by NSERC and the Science Foundation of Zhejiang Sci-Tech University (ZSTU) Grants No. 14062170-Y. Lin's work was mostly done during his sabbatical leave at the ZSTU. The authors are grateful to the anonymous reviewers for their insightful comments that improve the presentation greatly.
- Chang Y-C, Lee C-Y (2004) Machine scheduling with job delivery coordination. Eur J Oper Res 158:470–487MathSciNetCrossRefzbMATHGoogle Scholar
- Cheng B, Yang S, Hu X, Li K (2014) Scheduling algorithm for flow shop with two batch-processing machines and arbitrary job sizes. Int J Syst Sci 45:571–578MathSciNetCrossRefzbMATHGoogle Scholar
- Cheng TCE, Gordon VS, Kovalyov MY (1996) Single machine scheduling with batch deliveries. Eur J Oper Res 94:277–283CrossRefzbMATHGoogle Scholar
- Jr Coffmann EG, Galambos G, Martello S, Vigo D (1998) Bin packing approximation algorithms: combinatorial analysis. Kluwer Academic Publishers, Philip Drive NorwellGoogle Scholar
- de la Vega WF, Lueker GS (1981) Bin packing can be solved within \(1 + \epsilon \) in linear time. Combinatorica 1:349–355MathSciNetCrossRefzbMATHGoogle Scholar
- Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, San FranciscozbMATHGoogle Scholar
- Garey MR, Johnson DS (1985) A \(71/60\) theorem for bin-packing. J Complex 1:65–106MathSciNetCrossRefzbMATHGoogle Scholar
- Gong H, Tang L (2011) Two-machine flowshop scheduling with intermediate transportation under job physical space consideration. Comput Oper Res 38:1267–1274MathSciNetCrossRefzbMATHGoogle Scholar
- Johnson SM (1954) Optimal two- and three-machine production schedules with setup times included. Naval Res Logist 1:61–68CrossRefGoogle Scholar
- Lee C-Y, Chen Z-L (2001) Machine scheduling with transportation considerations. J Sched 4:3–24MathSciNetCrossRefzbMATHGoogle Scholar
- Lee C-Y, Strusevich VA (2005) Two-machine shop scheduling with an uncapacitated interstage transporter. IIE Trans 37:725–736CrossRefGoogle Scholar
- Maggu PL, Das G (1980) On \(2\times n\) sequencing problem with transportation times of jobs. Pure Appl Math Sci 12:1–6MathSciNetzbMATHGoogle Scholar
- Pinedo M (1995) Scheduling: theory algorithm and systems. Prentice-Hall, Englewoods CliffszbMATHGoogle Scholar
- Simchi-Levi D (1994) New worst-case results for the bin packing problem. Naval Res Logist 41:579–585MathSciNetCrossRefzbMATHGoogle Scholar
- Su C-S, Pan JC-H, Hsu T-S (2009) A new heuristic algorithm for the machine scheduling problem with job delivery coordination. Theoret Comput Sci 410:2581–2591MathSciNetCrossRefzbMATHGoogle Scholar
- Tang L, Guan J, Hu G (2010) Steel making and refining coordinated scheduling problem with waiting time and transportation consideration. Comput Ind Eng 58:239–248CrossRefGoogle Scholar
- Yue M, Zhang L (1995) A simple proof of the inequality \(\text{ MFFD }({L})\le \frac{71}{60}\,\text{ OPT }({L}) + 1\), \(\forall {L}\), for the MFFD bin-packing algorithm. Acta Mathematica Applicate Sinica 11:318–330MathSciNetCrossRefzbMATHGoogle Scholar
- Zhong WY, Dósa G, Tan ZY (2007) On the machine scheduling problem with job delivery coordination. Eur J Oper Res 182:1057–1072MathSciNetCrossRefzbMATHGoogle Scholar


text: Find Security Systems Near: Bloomfield Advance Security Systems Puxico Security Systems Sturdivant Security Systems Dexter Security Systems Bell City Security Systems Brownwood Security Systems Essex Security Systems Dudley Security Systems Mc Gee Security Systems Zalma Security Systems Local Results for Security Systems Advanced Communications & Technology: Division of Faith Enterprises, LLC 10.2 Miles Free Viasat-2 Satellite Internet Installation Dexter, MO 63841 View Phone Click to View Phone 573-775-7200 Toll free: 877-800-0230 Alternate: 573-722-7200 Interface Security System 16.7 Miles 619 S Walnut StBernie, MO 63822 View Phone Click to View Phone 573-293-6600 Medicare Information Social Security Administration Toll Free-Dial 1 & Then 25.3 Miles Malden, MO 63863 View Phone Click to View Phone 800-772-1213 Dittronics Inc 26.4 Miles 14 N WinchesterBenton, MO 63736 View Phone Click to View Phone 573-545-3912 LeGrand Technical Services 29.0 Miles Kelso, MO 63758 View Phone Click to View Phone 573-264-4516 Don't Know Who to Call? Searching for a qualified security system in your area? Call Us for Assistance: 1- Return to First-Page Security Systems Unfortunately, no results were found for your request. Please try again.


text:
Come experience the Hub of Central Oregon! Redmond is home to 300 days of sunshine, world class golf, antique shops galore, and impressive resorts, so come discover what makes Redmond so special!
From the majesty of Smith Rock and the Crooked River Canyon to the quaint shops and delicious restaurants downtown, Redmond has something for everyone.
Getting here is easy with the region's only commercial airport: Robert's Field (RDM), featuring non-stop service to seven exciting cities, creating adventure both near and far!
Come discover how close Redmond is to all the wonders of Central Oregon!
Top Fares From
Today's Top Travel Deals
Brought to you by ShermansTravel
Ireland: 9-Nt Self-Drive Trip, Incl. Cliffs...
Tourism Ireland / Great Value Vacationsvacation $1274+
Jamaica: Sandals All-Inclusive Resort w/Up To...
Avoya Travelhotel $550+
Montréal to Miami: Luxe 16-Nt Cruise,...
Oceania Cruisescruise $3299+


text:
Fluctuating Gold - This option will add an additional random amount of gold to merchant inventories so that merchants don't always have a static amount of gold. This will be added to their base gold, so they will always have at least the base amount available. The random amounts have been set with regard to the vanilla gold amount and won't increase merchant gold drastically above the vanilla amounts.
Check online swap markets and online auctions that have a bartering component such as Craigslist.com (check under "For Sale" for the Bartering category), Swapace.com, SwapThing.com, Barterquest.com, U-Exchange.com, Trashbank.com and Ourswaps.com. Check for local bartering clubs. Your local Chamber of Commerce may be able to provide you with information on similar clubs in your area.
For instance, each time Apple releases a new version of the iPhone, the second-hand market for older versions of the iPhone enjoys a flurry of activity. However, you do have to be as careful with the barter of used goods as you would be with the purchase of used goods. Be sure everything is in working order and shows no signs of significant damage.
Advertiser Disclosure: The credit card offers that appear on this site are from credit card companies from which MoneyCrashers.com receives compensation. This compensation may impact how and where products appear on this site, including, for example, the order in which they appear on category pages. MoneyCrashers.com does not include all credit card companies or all available credit card offers, although best efforts are made to include a comprehensive list of offers regardless of compensation. Advertiser partners include American Express, U.S. Bank, and Barclaycard, among others.
As Orlove noted, barter may occur in commercial economies, usually during periods of monetary crisis. During such a crisis, currency may be in short supply, or highly devalued through hyperinflation. In such cases, money ceases to be the universal medium of exchange or standard of value. Money may be in such short supply that it becomes an item of barter itself rather than the means of exchange. Barter may also occur when people cannot afford to keep money (as when hyperinflation quickly devalues it).[14]
I have made every attempt to keep this mod as compatible as possible with all other mods, and it should be fully compatible with nearly every mod out there. There are a few features that may conflict, but these can be toggled off to maintain compatibility. The features will work just fine with merchants added by other mods (assuming they've been placed in the proper factions). In fact, while this mod does work very well on it's own, my primary intention was to create a mod that would compliment and enhance existing mods that already overhaul Skyrim's economy.
Economists since the times of Adam Smith (1723-1790), looking at non-specific pre-modern societies as examples, have used the inefficiency of barter to explain the emergence of money, of "the" economy, and hence of the discipline of economics itself.[3] However, ethnographic studies have shown that no present or past society has used barter without any other medium of exchange or measurement, nor have anthropologists found evidence that money emerged from barter, instead finding that gift-giving (credit extended on a personal basis with an inter-personal balance maintained over the long term) was the most usual means of exchange of goods and services.[4]
SOME SUGGESTIONS - With all these different variables, you may be wondering what the best settings are to achieve a good balance in your game. Of course this will depend on what you want. Many people (myself included) like to make trade more difficult. I also like to set the barter settings relatively close to de-emphasize Speech skill and place more importance on the Speech perks.
Advertiser Disclosure: The credit card offers that appear on this site are from credit card companies from which MoneyCrashers.com receives compensation. This compensation may impact how and where products appear on this site, including, for example, the order in which they appear on category pages. MoneyCrashers.com does not include all credit card companies or all available credit card offers, although best efforts are made to include a comprehensive list of offers regardless of compensation. Advertiser partners include American Express, U.S. Bank, and Barclaycard, among others.
1.Jump up ^ O'Sullivan, Arthur; Steven M. Sheffrin (2003). Economics: Principles in Action. Pearson Prentice Hall. p. 243. ISBN 0-13-063085-3. 2.^ Jump up to: a b Graeber, David (2011). Debt: the first 5,000 years. New York: Melville House. pp. 21–41. 3.Jump up ^ Humphrey, Caroline (1985). "Barter and Economic Disintegration". Man 20 (1): 49. 4.^ Jump up to: a b Humphrey, Caroline (1985). "Barter and Economic Disintegration". Man 20 (1): 48. 5.Jump up ^ Humphrey, Carolyn and Stephen Hugh-Jones (ed.). Barter, Exchange and Value: An Anthropological Approach. Cambridge: Cambridge University Press. p. 3. 6.Jump up ^ Graeber, David (2001). Toward an Anthropological Theory of Value: The False Coin of our Dreams. New York: Palgrave. p. 154. 7.Jump up ^ Graeber, David (2011). Debt: the first 5,000 years. New York: Melville House. pp. 40–41. 8.Jump up ^ Graeber, David (2001). Toward an Anthropological Theory of Value: The false coin of our own dreams. New York: Palgrave. pp. 153–4. 9.Jump up ^ Graeber, David (2011). Debt: The First 5,000 Years. Brooklyn, NY: Melville House. pp. 94–102. 10.Jump up ^ Robert E. Wright and Vincenzo Quadrini. Money and Banking.Chapter 3, Section 1: Of Love, Money, and Transactional Efficiency Accessed June 29, 2012 11.Jump up ^ Humphrey, Caroline (1985). "Barter and Economic Disintegration". Man 20 (1): 66–7. 12.Jump up ^ Plattner, Stuart (1989). Plattner, Stuart, ed. Economic Anthropology. Stanford, CA: Stanford University Press. p. 179. 13.Jump up ^ M. Bloch, J. Parry (1989). Money and the Morality of Exchange. Cambridge: Cambridge University Press. p. 10. 14.Jump up ^ Humphrey, Caroline (1985). "Barter and Economic Disintegration". Man 20 (1): 52. 15.Jump up ^ Polanyi, Karl (1957). Polanyi, Karl et al, ed. Trade and Market in Early Empires. Glencoe, Illinois: The Free Press. p. 14. 16.Jump up ^ Harrison, John (1969). Quest for the New Moral World: Robert Owen and the Owenites in Britain and America. New York: Charles Scibners Sons. p. 72. 17.Jump up ^ Harrison, John (1969). Quest for the New Moral World: Robert Owen and the Owenites in Britain and America. New York: Charles Scibners Sons. p. 73. 18.Jump up ^ Harrison, John (1969). Quest for the New Moral World: Robert Owen and the Owenites in Britain and America. New York: Charles Scibners Sons. pp. 202–4. 19.Jump up ^ Tadayuki Tsushima, Understanding "Labor Certificates" on the Basis of the Theory of Value, 1956 20.Jump up ^ Homenatge A Catalunya II (Motion Picture). Spain, Catalonia: IN3, Universita Oberta de Catalunya, Creative Commons Licence. 2010. Retrieved January–2011. "A documentary, a research, a story of stories about the construction of a sustainable, solidarity economics and decentralized weaving nets that overcome the individualization and the hierarchical division of the work, 2011." 21.Jump up ^ Barcelona's barter markets (from faircompanies.com. Accessed 2009-06-29.) 22.Jump up ^ "What is LETS?". AshevilleLETS. Retrieved December 9, 2008. 23.Jump up ^ TIMES, nov. 2009 24.Jump up ^ David M. Gross, ed. (2008). We Won't Pay: A Tax Resistance Reader. pp. 437–440. 25.Jump up ^ Tax Topics - Topic 420 Bartering Income. United States Internal Revenue Service
An alternate currency, denominated in labour time, would prevent profit taking by middlemen; all goods exchanged would be priced only in terms of the amount of labour that went into them as expressed in the maxim 'Cost the limit of price'. It became the basis of exchanges in London, and in America, where the idea was implemented at the New Harmony communal settlement by Josiah Warren in 1826, and in his Cincinnati 'Time store' in 1827. Warren ideas were adopted by other Owenites and currency reformers, even though the labour exchanges were relatively short lived.[20]
Nowinska says one of the biggest challenges Swapsity faces is that new barterers think they have nothing to offer. So they offer bad trades. Yet most people have hundreds of skills—from cooking to networking to scrapbooking. The trick is learning to recognize the value of your skills, your knowledge and your talent. Bartering attaches value to things that are not always recognized, or highly valued, in a cash economy—often hobbies that people can't make a living on but love to do. One Barter Babe trades her homemade canned goods for gifts—mostly other crafted items—she can give away at Christmas. A Swapsity member has traded pounds of fiddleheads she picks at her mom's house in the country for feng shui sessions.
The Buy-day (Wheat) Ecological Life Associate summarizes a vision of life in Gezi as follows: "In our world, which is being poisoned and destroyed by consumer culture, we need sustainable and self-operating models of lifestyles, including a barter economy, ecological food production, arts and craftsmanship based on needs, renewable and effective energy use, agricultural models backed by society, permaculture, slow cities, transitional towns, eco-villages, district gardens and secondhand and recycling systems.
When exchanging services, it's important to remember that bartering is considered income. While you may be able to write off expenses you incur during the barter, you must claim the fair market value of the services you provided as income. For example, if you charge $60 an hour as a massage therapist, and you trade a one-hour massage for housecleaning services, you may have to claim the equivalent income. When you trade assets, you may even be responsible for tracking capital gains or losses. If you have any doubts or questions, consult the IRS website.
The man who arguably founded modern economic theory, the 18th-century Scottish philosopher Adam Smith, popularized the idea that barter was a precursor to money. In The Wealth of Nations, he describes an imaginary scenario in which a baker living before the invention of money wanted a butcher's meat but had nothing the butcher wanted."No exchange can, in this case, be made between them," Smith wrote.
Barter Economy had a long history of evolution. It was introduced in the pre-historic times for the systemization of the production and distribution of commodities and services among the existing population. In recent times, this age-old economic concept is widely prevalent among pre-market and pre-capitalist economies. A deep sense of reciprocation, together with substitution of the redistribution for market exchange characterizes Barter Economy currently.
In late 2012, Toronto even got its own spinoff of Trade School, a model that originated in New York in 2010. The Toronto Trade School holds classes—on anything from spoken word to origami flower–making to bicycle maintenance—and invites students to "pay" with an item or service from the teacher's barter wish list. It has hosted more than 70 classes.
Adam Smith, the father of modern economics, sought to demonstrate that markets (and economies) pre-existed the state, and hence should be free of government regulation[citation needed]. He argued (against conventional wisdom) that money was not the creation of governments. Markets emerged, in his view, out of the division of labour, by which individuals began to specialize in specific crafts and hence had to depend on others for subsistence goods. These goods were first exchanged by barter. Specialization depended on trade, but was hindered by the "double coincidence of wants" which barter requires, i.e., for the exchange to occur, each participant must want what the other has. To complete this hypothetical history, craftsmen would stockpile one particular good, be it salt or metal, that they thought no one would refuse. This is the origin of money according to Smith. Money, as a universally desired medium of exchange, allows each half of the transaction to be separated.[3]
Economic historian Karl Polanyi has argued that where barter is widespread, and cash supplies limited, barter is aided by the use of credit, brokerage, and money as a unit of account (i.e. used to price items). All of these strategies are found in ancient economies including Ptolemaic Egypt. They are also the basis for more recent barter exchange systems.[17]
The same thing holds true of all other possessions; for barter, in general, had its original beginning in nature, some men having a surplus, others too little of what was necessary for them: hence it is evident, that the selling provisions for money is not according to the natural use of things; for they were obliged to use barter for those things which they wanted; but it is plain that barter could have no place in the first, that is to say, in family society; but must have begun when the number of those who composed the community was enlarged: for the first of these had all things in common; but when they came to be separated they were obliged to exchange with each other many different things which both parties wanted.
Default - These are preselected values. See the Race Relationships chart in Images to view what the default race settings are. There are also some locational differences. As the cosmopolitan capital, residents of Solitude express less racism than elsewhere in Skyrim. However, Nords who are residents of Windhelm or part of the Stormcloak faction express stronger racism. I've also built several exceptions into the default settings to reflect individual character traits present within the game. Also, your personal relationship with a merchant is more important than any general feelings they may have toward your race and will override any general racial bias.
STOLEN GOODS - Don't expect any favors from Fences. Selling stolen items is going to cost you, so don't expect to get top dollar for ill-gotten goods. Tonila is exempt (actually all Thieves Guild & Dark Brotherhood fences are exempt, but in the vanilla game this just applies to Tonila). Any mod-added merchants who have been made members of the Thieves Guild or Dark Brotherhood faction will also be exempt. Options: -25% to -5% worse prices.
Identify your resources. What items do you have that you could easily part with? Use a critical eye to go through your home, and consider possessions you may have in storage or that another family member or friend is currently using. If you would prefer to offer services, honestly assess what you could provide for others that they would otherwise pay a professional to do. It could be a skill or a talent or hobby such as photography.


text:
Employment and Internship Opportunities at the Texas Department of Licensing and Regulation
On this page:
TDLR employs 426 people in a wide variety of professional, administrative and technical positions and provides a total compensation package that enables us to attract, motivate, and retain highly skilled and talented employees. Our employees also enjoy agency and state benefits and the opportunity to contribute toward TDLR's vision of being the leader in public service by creating innovative, low cost and regulatory best practices, and cultivating employees who provide exceptional customer service.
TDLR was recognized as the Model Regulatory Agency for the state of Texas in its last Sunset Commission review and ranked one of Austin's Top 25 Mid-Sized Employers by the Austin American-Statesman in 2010, 2011 and 2013. Additionally, the Texas Quality Foundation recognized TDLR with the Foundation's Progress Level Award for outstanding organizational management and performance in 2011.
Please scroll below to find current openings. You can also sign up to receive email notices when new job openings are posted. To learn more about TDLR's mission, goals, and what we do, please visit our Compact with Texans page. If you have any questions or comments, please call the Human Resources Office at 512-463-7184.
Internships with TDLR
The TDLR Internship program is an opportunity for students to gain practical and meaningful work experience. You will learn and develop marketable skill sets and be exposed to valuable networking prospects. A promising career in the public sector awaits you and the TDLR Internship Program would like to assist you in getting there.
Applying for Jobs with TDLR
To apply for a job with TDLR, please submit a TYPED State of Texas Employment Application. Applications are only accepted for posted positions and must be submitted by 5 p.m. on the closing date.
The necessary forms and information for applying with TDLR can be found here:
- State of Texas Employment Application
- Instructions for Completing the State of Texas Application for Employment
- Employment History Continuation Sheet
Current Openings
Web Administrator II – Austin
Posting Number: 0105-19
Group/Step: B20, Position 311
Opening Date: 01/11/19
Closing Date: until filled
$51,912- $56,616 annually
Building and Mechanical Multi-Program Specialist (Program Specialist III) – Austin
Posting Number: 0303-19
Group/Step: B19, Position 65
Opening Date: 03/05/19
Closing Date: until filled
$42,244.08-$52,700.04 annually
Deputy Chief Elevator Inspector (Program Specialist V) – Austin
Posting Number: 0306-19
Group/Step: B21, Position 51
Opening Date: 03/14/19
Closing Date: until filled
$48,278.04-$63,132 annually
Payroll Officer (Accountant V) – Austin
Posting Number: 0402-19
Group/Step: B21, Position 454
Opening Date: 04/12/19
Closing Date: 5 p.m. on 04/26/19
$51,624-$63,500.04 annually
Field Inspector (Inspector IV) – Denton County and Surrounding Areas
Posting Number: 0403-19
Group/Step: B15, Position 108
Opening Date: 04/22/19
Closing Date: 5 p.m. on 5/6/19
$40,800 annually
TDLR offers a unique culture that unites the traditional benefits of working for the state with the agency's innovative efforts to provide our employees a great work environment.
Explore these links to learn about the benefits available to our employees.
Staff Compensation Information, as required by Government Code, Section 659.026.


text:
About the Owner, Steve
RV adventures are a huge part of my life. You will love the relaxation and adventure you will experience when you go out on the road and experience RV life. I hope you enjoy your experiences as much as I do. It truly is memory making at its best! Enjoy!


text:
A Proper Mess (2018)
A Proper Mess
Title: A Proper Mess (2018)
Director Angel Long
Starring Alexxa Vice, Angel Long, Lucia Love, Misha Cross, Sophie Anderson, Antonio Black, Frank Crass, Marc Rose, Mr Longwood
Time 2 hours 25 minutes
Released DVD 2018-11-07
Genre Pornstar, Lesbian, Hardcore, Anal, Deepthroat, Facial, Blowjob, Solo Masturbation, Brunette, Tattoo, amp, Piercing
A Proper Mess Summary: Angel Long's "A Proper Mess" is the work of a filthy mind. As she provokes spit-soaked anal perversion from behind the camera, her running commentary heightens the nastiness, despite (and because of) her elegant English accent. Dominant Angel gags, slaps and fingers pale, natural Misha Cross. Angel shoves Misha's head down on Marc Rose's big boner for a BJ and then up his ass for a rim job. He buttfucks Misha into the floor as she eats Angel's pussy. Frank Cross spits in tattooed, pierced Alexxa Vice's face, and aggressive throat fucking creates cascading rivers of slobber. His stiff meat goes straight to anal. Foul-mouthed Sophie Anderson treats Antonio Black's big black cock to a graphic, deep-throat blowjob. Her enormous jugs jounce as he slam-fucks her sphincter; extreme sodomy comes with ass-to-mouth cocksucking, immense rectal gaping and deep pussy plowing. Angel and Mr Longwood each cram three fingers into naturally buxom Lucia Love's asshole at once. Slobber flows and her reddened eyes water. She gargles cum, blows bubbles and licks spunk from the floor to climax a slaphappy, slobbery interracial mess.
Angel Long's "A Proper Mess" is a single-disc DVD with behind-the-scenes footage, cumshot recap, cast list and filmography.
A Proper Mess (2018) | Download NOW !


text:
RIGS 2019 Annual Meeting & Book Sale
On Sunday, May 19, 2019 at the North Kingstown United Methodist Church, from 1:00 pm to 3:00 pm, RIGS will hold its Annual Meeting, which includes the election of the 2019-20 Board of Directors. Details of the meeting can be found in the April Newsletter:
Richard Bowen (Vol. 1) Sold Out
The Richard Bowen Book (Vol. 1) is no longer available as it has sold out.
New Book:
John Clarke's World
now available in the Online Store
by Cherry Fletcher Bamberg FASG and Judith Crandall Harbold
RI Roots and Gleanings Back Issues
RI Roots and Gleanings back issues pdf's are now available to members only.
They are in the Downloads (Members Only) section of our website.
Fourth Volume of Richard Bowen of Rehoboth, Massachusetts and His Descendants now available
by William B. Saxbe, Jr., CG, FASG
The Rhode Island Genealogical Society is delighted to announce the publication of the fourth volume of the critically acclaimed book Richard Bowen (1594?-1675) of Rehoboth, Massachusetts and His Descendants. This short volume has additions and corrections of the first three volumes.
© 2019 Rhode Island Genealogical Society
Design by Webworx Design Group
Powered by EasyNetSites.com Webware


text:
Fri. Feb. 8, 2019
Art, All Ages
Create an original, wearable or decorative Mardi Gras Mask just in time for the PAC's Mardi Gras Party. Register by Feb. 1st! $30 per person *Workshop includes an unpainted Mardi Gras Mask and basic decorations. Complimentary Glass of Wine or a beer or a soda.
Feel free to bring embellishments , such as beads, feathers, trim, jewels, sequins, glitter, etc. and a glue gun with glue sticks.
Sat., April 27th, 2019
Community Event, All Ages
Join in on the "Trashion Show" fun by designing a recycled article of clothing or come and see the creative results at the show!
May 4, 2019
Theatre, All Ages
Sat., May 4, 2019, Broadway Comic Murder Mystery, "The Play That Goes Wrong," Appleton PAC
May 10, 2019 - August 3, 2019
Art, All Ages
The power of the oceans, inland seas, and rivers is unlimited. Accessibility to water enables the founding and sustaining of civilization in wildly diverse locations across the planet. We are charged with the continuous preservation of this, our most important resource. Artists are invited to enter original works with a personal view of its impact.
Newsletter Sign-Up


text:
Top 100 Love Quotes
These are our best quotes, listed by their user rating. We value your opinion and allow you to rank each quote.
I know that my feelings for you are real because I spend more time thinking of you than myself.
Missing you is my hobby, caring for you is my job, making you happy is my duty and loving you is my life.
You see, I love you and I don't want to lose you because my life has been better since the day I found you.
They say you only fall in love once, but that can't be true. Every time I look at you, I fall in love all over again.
So many reasons are there to love you. Your cute smile, your sweet laugh, your innocence and your kind heart makes me love you.
This is from my heart, to thank you for everything you have done for me, for all the times I forgot to tell you how I feel about you and how happy I am that you are in my life.
Imagining a life without you is something that is impossible, you make me complete and I want you to know you mean everything to me.
Today and always, beyond tomorrow, I need you beside me, always as my best friend, lover and forever soul mate.
No matter how much time I spend with you, I can never ever get enough of you. Your love is forever mine and I need you everyday.
When I miss you, I read our old conversations, smile like an idiot, listen to songs that remind me of you, then I miss you more.
My love for you is a journey starting at forever and ending at never.
If you're asking if I need you, the answer is forever. If you're asking if I will leave you, the answer is never. If you're asking what I value, the answer is you. If you're asking if I love you, the answer is I do.
A good morning text doesn't only mean "Good Morning." It has a silent message that says "I think of you when I wake up."
One smile can start a friendship. One word can end a fight. One look can save a relationship. One person can change your life.
I feel like everything in my life had led me to you. My choices, my heartbreaks and my regrets. Everything. And when we're together, my past seems worth it. Because if I had done one thing differently, I might never have met you.
Ever since the day you came in my life, I know that you are the one I'll truly love till the end.
- 1
- 2
- 3
- 4
- Next Page »


text:
Upcoming Events › MusiCore
Events Search and Views Navigation
April 2019
MusiCore Germantown – Volunteer Orientation & Training
Rock to the Future is always looking for volunteers to mentor our students and help with homework in MusiCore after school programs. Be a positive role model and have a huge impact in the lives of the kids and teens we work with! Volunteer orientations give new volunteers an overview of Rock to the Future and the MusiCore program and introduce volunteers to the tasks they'll be helping with. The academic success of our students is extremely important to us,…Find out more »
June 2019
Rock to the Future MusiCore After School Year End Showcase
Rock to the Future proudly presents its 9th Annual MusiCore Year End Showcase, featuring performances by student bands and choral ensemble from the MusiCore After School program. Philadelphia students from Rock to the Future's Kensington and Germantown locations will take the stage with their bands to show off the music they created and learned this year. Celebrate the talents and achievements of Philadelphia youth at this FREE, family friendly event! Doors are 10:30am with the performances running from 11am -…Find out more »


text:
Page valign middle css jobs
...designer who can help us create these items from scratch with our guidance. The designer should have a blend of creativity, innovation and with high taste and preferably with Middle Eastern culture knowledge. Example of products: Candlesticks Coasters Tealight holders Photo frames Mirrors Gift/Souvenir items Notebooks Table accessories Indoor plant
I need someone to fix one CSS issues which I will explain . Website is built on Slim framework. Bid only if you can work right now.
...two different Bootstrap versions are used due to sperate themes of the pages. In website, PHP syntax is used so same Header and Footer so to include on every different theme page used in the website. Task needs to be done (New fixes) 1.) Need to add new theme Pages that will be provided by me and slice header and Footer so to Include existing Header
I would like a credit card to be designed same as the pictures that I uploaded. I need my r...1 and without any text and boarder which is similar to image number 2. So the end result is similar to image number 1 but without text and a crown image like image 2 in the middle. But the colors I need it to be in black and white with transparent background.
I currently have a website where I need to move some images around, add a english/french dropdown and move some text around. I am having issues getting things to allign
We have existing HTML code and need modifications to the layout, including color changes, fonts, logos, icons and most importantly, to implement JQuery on buttons, tabs, carousels, etc.
...prevent default reload of the page on action and notify form response in a div according to website theme. Form should be serialized and validated. Data is handled by MySQL/PHP, client side javascript/jquery should make ajax call to server-side processing script for adding, removing and saving data without refreshing the page. Please contact me for more
Two 3D Make the Motrin bottle orange and use the orange bootle to complete the graphics like we did on the Tylenol. All...rubber on the cap. Once the video shows the label have the bottle go on the shelf that has just motrin on it. 3 different sizes , Small 75 count on top shelf, medium 150 on middle shelf, and large 250 count on the bottom shelf.
I need the pre existing image to have the writing removed - Then In the middle say '' 28 day challenge'' ''lose up to 5kgs'' - In very good writing. - also need it - This is for a facebook ad Image size: 1200 x 628 pxl Square Size: 1080x 1080pxl
Experience on BootStrap - Excellent on web technologies including HTML, CSS, JavaScript, AJAX Jquery - Very good knowledge of databases MySQL - Experience in common third-party APIs (Google, Facebook, Ebay etc) - Strong debugging skills - Excellent English writing and speaking skills are a must
First deep study on Consultancy Service before making content page or how outsourcing business works for managing employees for other companies. 5 paragraph on our service for Outsourcing employee / candidate with management In India How we work for companies providing candidates for interview. How we manage candidate data and manage salary on our
Hi, I need a custom complex scrollbar for today. CSS and/or JS/JQUERY
...Custom Field that displays a table (Custom Meta Box). Need another plugin here that fits better. - I add social media buttons and WP Accesssibility Text Resize buttons that need CSS optimaziation and fixing - Fix a GMap zoom level (flexible zoom level?) - Fix WPUF plugin Custom Fields in Backend. Change plugin? - Fix an issue that it is not possible to
We are in middle of developing one app in flutter, although we get few issues. More details will be shared in chat. Expecting work of around 2-3 hours.
...functioning website already with admin panel. We would like to add Ten (10) features to the site. 1. Home Page Ad Banner with search bar (banner must be changeable from admin) 2. Adding New menu to the top menu list (every added menu will have its own result page) 3. Ad Banner on the left (this banner is controllable by the admin. format type should be image
... Queens Carlton Project - Remove the words construction commenced Explore the Collection Section - Change photograph to the below image Remove a price list on another page...
its too urgent work most of the work has been done . there are total 17 pages which need css work . dont bid new freelancer as i have suffered a lot in past few days with some unskilled devs . design is in adobe fire works only bid if you can complete it by today night or by tomorrow morning and can start right now . dont bid company only need a
...and necromancy. In fact the title is "the necromancer" I need something eye-catching and dark. satanic even a little. The story is set in the middle of nowhere by a river. What i need to see if the location, middle of nowhere, some satanic shit, maybe a fire burning somewhere and perhaps a man in a long black trench coat with a cigarette in his mouth.
...Fusion program which can be found at Lumapix.com. They have a free trial version to download for viewing the features of the program. There should be sections for elementary/middle school yearbooks as well as high school yearbooks. The program is for English speaking people, however It also needs to be able to support Hebrew Fonts for some Hebrew wording
Coding Knowledge requirements: MySQL 4.8.5, PHP. 7, Html 5.1, CSS 4, jQuery 3.4.0, Ajax, Apache web server 2.4, Amazon Web Service Ec2,etc. All Html files have been created and are on the server. The server has been configured with latest Mysql and latest PHP. The MYSQL database in empty and you will need to create the corresponding tables, with regards
...jpg") When it is between 481px and 768px, the "Edition: MAIN | CANADA" line it becomes obscured by other elements. (see uploaded image "[login to view URL]") I need you to write the CSS code to correct this so that the "Edition: MAIN | CANADA" line IS visible UNTIL 768px. Once the viewport is 768 or larger, it should remain invisible. You won'...
fix some simple css wordpress site bugs.
...The idea I have in mind is a Tiger of some sort, appearing to be on the hunt/prowl in a stalking posture. The main concept I am trying to grab is a hard outlined tiger in the middle, with 4 fading tigers on both sides of the main tiger. To give the illusion of being 9 tigers or the 9 lives. As far as the lettering, it can be placed in the center of the
I am a freelance copywriter specializing in white papers for b2b businesses. It is a very untapped market and I am in the middle of building a website for my business and need a logo. I have the design in my head and will do my best to describe it and will provide photos to illustrate. The name of my business is WhitePaperWolf. The idea for a logo I
I have a page previously created in a custom build via a psd file we have. We need some minor updates completed immediately. This project is for someone who can start and work throughout the day today
need buyers for my product carpets from middle east specifically.
Need to develop a landing page through brochure
...our Concept. We need Web Business design (and short video) that is easy to grasp and create needs to use us. In simple: We are in the B2B, B2G and G2G business for small, middle and big size Companies at Local (City level) National and Global level. We have Free text embedded Search Engine in all our websites. In addition, a Field based Database for
need some CSS help for my site quickly
company emails often have a certain composition form...'_' + ln, fn, """"" Where fn = firstname, ln = lastname, mn = middlename, fi = first letter of firstname, li = first letter of lastname, mi = first letter of middle name List of firstnames, lastnames and middlenames will be provided. Test list of emails will be provided as well.
the business is a website that will allow people to take doctor appointments and manage their medical file The name of the company is Mowadoc mowa is appoint...people to take doctor appointments and manage their medical file The name of the company is Mowadoc mowa is appointment and Doc is for doctor the company will start in the Middle East
Project Deadline: 1 HOUR ONLY Project Type: CSS Bug Fix Experience Level: Expert Bug Details: We have an image gallery slider on our website ([login to view URL]). On Firefox, Mobile & All other browsers this works fine. Navigation arrows work fine. On Chrome only the navigation arrows (Next/Previous) do not work. Using the keyboard arrows to change
Two Logos. First for Ramblin Roy's Restaurant and Nightclub. Must not have any clip art from the internet. Needs to have either sketches drawn digitally (your...where dancing is the most fun! Please see attachments, need someone to sketch or photoshop and blend middle section.
I want designs for tv sets - coffee tables - tables service - shoe organizer - corner coffee shelves - wooden entrances white color - table middle living room
We have a requirement to develop a native iOS and Android app for an insurance company in Middle East.
Project Deadline: 1 HOUR ONLY Project Type: CSS Bug Fix Experience Level: Expert Bug Details: We have an image gallery slider on our website ([login to view URL]). On Firefox, Mobile & All other browsers this works fine. Navigation arrows work fine. On Chrome only the navigation arrows (Next/Previous) do not work. Using the keyboard arrows to change
...machine-readable zone and human-readable zone (passport number, name, surname, e.t.c) In internal passport of Russian federation scanned pictures, rotated pictures, phone photo (middle quality, shadows, light, blur) languages c/c++/c#/python/up to you can you do it? what time do you need for project? what price (per hour/for whole project) do you need
...functioning website already with admin panel. We would like to add Ten (10) features to the site. 1. Home Page Ad Banner with search bar (banner must be changeable from admin) 2. Adding New menu to the top menu list (every added menu will have its own result page) 3. Ad Banner on the left (this banner is controllable by the admin. format type should be image
Hi I am after creating a logo for my cosmetic enhancments buisness. Name : Elite cosm...creating a logo for my cosmetic enhancments buisness. Name : Elite cosmetic enhancements Something simple e.g. gold metalic circle with initial e in the middle and In black running through the middle my company name in black I have attached some inspiration.
Hi freelancers.. Budget for this job $10 I have a WP forms form installed on my website. I need someone to style it to match. It should be a simple CSS job. It is using the DIVI page builder. The form itself does not show up until you are viewing the live site. I will send all the details. Budget for this job $10
Hi I'm am just after a simple logo made for my cosmetic enhancment buisness I'm am opening. Only af...made for my cosmetic enhancment buisness I'm am opening. Only after something simple and t ooo appeal to both genders I like the gold symbol with black writting through the middle. Have you an email add I can send photos of roughly what I am after?
I need a complete HTML5, bootstrap, JS, CSS responsive website. It should be functional on all major browsers such as: Safari, IE, Edge, Chrome, FireFox, as well as mobile device browsers not mentioned. The website might be up to 5 pages, but may also just contain some of the content as sections in one page (various pics that you can use in the pics
I need to adapt the layout / look&feel of the Zoho Helpd Desk self service portal with colors / layout inspired on our website. The ideia is to keep it very simple and pragmatic just mimiking our website standar colors and fonts and using a classical FAQ style type of layout our company site: [login to view URL] an ideia of a simple FAQ layout that I like just as an example ([login to ...
I want app that people can register and sell their online accounts or stuff and people can buy them i want the app in arabic language.
...opening. The two outside panels are part of the elevator. The two inside panels are the doors. They move vertically with the elevator. They open horizontally by splitting in the middle and moving outward, overlapping the side areas. They close by moving back together. The doors should be simple solid surfaces, of a different color than the elevator itself
...myself, i would like to edit it to also cut down on costs in an ethical way without being cheap about it. It's not exactly classified as a wedding or an engagement, in the middle... an elopement. A private event. We don't need anything extra, you can shoot on my cards or copy onto my computer~ Please know i don't want you to feel like I'm taking
Create a ettiket in PSD CSS based on PNG File has to be editable and font family has to be saved.. Couple of small and big projects coming. TNX
I want to make a small modification for my website header to make the logo appear on the middle of the menu buttons.. The script is WordPress The theme is TheNa from envato