We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = b, l <= x <= u, x is an element of Z(r+ns)} where the constraint matrix A is an element of Z(ntxr+ns) consists of n matrices A(i) is an element of Z(txs )on the vertical line and n matrices B-i is an element of Z(txs )on the diagonal line aside. We show a stronger hardness result for a number theoretic problem called QUADRATIC CONGRUENCES where the objective is to compute a number z <= y satisfying z(2) alpha mod beta for given alpha, beta, gamma is an element of Z. This problem was proven to be NP-hard already in 1978 by Manders and Adleman. However, this hardness only applies for instances where the prime factorization of beta admits large multiplicities of each prime number. We circumvent this necessity proving that the problem remains NP-hard, even if each prime number only occurs constantly often. Using this new hardness result for the QUADRATIC CONGRUENCES problem, we prove a lower bound of 2(2 delta(s+t)) vertical bar I vertical bar(O(1)) for some delta > 0 for the running time of any algorithm solving 2-stage stochastic ILPs assuming the Exponential Time Hypothesis (ETH). Here, vertical bar I vertical bar is the encoding length of the instance. This result even holds if r, parallel to b parallel to(infinity), parallel to c parallel to(infinity), parallel to l parallel to(infinity) and the largest absolute value Delta in the constraint matrix A are constant. This shows that the state-of-the-art algorithms are nearly tight. Further, it proves the suspicion that these ILPs are indeed harder to solve than the closely related n-fold ILPs where the constraint matrix is the transpose of A.